AOJ1060 No Story

問題リンク No Story

• 解法

分からなかったので解説を見ました(解説の「遅い解法」の方法で攻めていました）。
Lを素因数分解して、
L = p0^e0 * p1^e1 ...
とします。すると、a, bはこの指数を決めて得られる整数となります。
また、LCM(a, b)がLとなるには、全ての指数eiについて、aとbの指数の大きい方がLのeiと一致すればいいことになります。aに相当する指数を決めてしまうと、LCM(a, b)=Lを満たすような整数bが何通りあるかは計算で求めることができます。
この方法だと、a > bのパターンもカウントしてしまっているのでダメです。2で割ろうとすると、1度しか計算されないa==bの分まで減らしてしまってアウトです。ですが、a==bでLCM(a, a)=Lを満たすようなものはLCM(L, L)=Lしかあり得ないし、これは必ず1回登場します。なので、答えを+1してから2で割れば正しく答えが求められます。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//No Story
public class AOJ1060 {
	
	int[] c;
	int n, res;
	
	void dfs(int k, int r){
		if(k==n){
			res+=r; return;
		}
		for(int i=0;i<c[k];i++)dfs(k+1, r);
		dfs(k+1, r*(c[k]+1));
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int N = 1000000;
		boolean[] p = new boolean[N+1];
		Arrays.fill(p, true);
		p[0]=p[1]=false;
		List<Integer> l = new ArrayList<Integer>();
		for(int i=2;i<=N;i++)if(p[i]){
			l.add(i);
			for(int j=i+i;j<=N;j+=i)p[j]=false;
		}
		for(;;){
			long L = sc.nextLong();
			if(L==0)break;
			c = new int[100];
			n = 0;
			int i = 0;
			while(L!=1&&i<l.size()){
				long x = l.get(i);
				if(L%x==0){
					while(L!=1&&L%x==0){
						c[n]++;
						L/=x;
					}
					n++;
				}
				i++;
			}
			if(i==l.size()){
				c[n] = 1; n++;
			}
			res = 0;
			dfs(0, 1);
			System.out.println(++res>>1);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1060().run();
	}
}