TopCoder SRM 713 Div1 Easy PowerEquation、Div2 Medium PowerEquationEasy

EasyもMediumも1発AC取れたので、参加しておきたかったね。
https://community.topcoder.com/stat?c=problem_statement&pm=14573
https://community.topcoder.com/stat?c=problem_statement&pm=14575

問題

正整数Nが与えられる。
A,B,C,Dを[1,N]の範囲の正整数とする。
A^B=C^Dとなる組み合わせは何通りあるか。

解法

A=C=1の場合だけはコーナーケースで先に処理する。
このときはB,Dはどの値でもよい。

それ以外の時を考える。
他の整数の(2乗以上の)累乗ではない整数をpとし、A=p^a、C=p^cと表現できるとする。
A^B=(p^a)^B=p^(aB)、C^D=(p^c)^D=p^(cD)より、aB=cDとなるa,B,c,Dの組み合わせを求める問題となる。

pを決めたとき、p^k≦Nとなるkの上限を考える。
するとa,cは1～kの間の値を取れる。p!=1なので、kは高々logNであり、そんなに組み合わせが多くない。
よってpを総当たりし、(a,c)の対を数え上げよう。

f(a,c) := pを[1,N]のうち他の数の累乗でない数で総当たりしたとき、(a,c)のとりえる対の組み合わせ

pは一見[1,N]を総当たりしないといけないように見えるが、p＞√Nであるpに対してはa=c=1の一択しかないのでそれらはまとめて処理すればよい。
すなわち、(√N～N]の範囲の整数から、すでに他の整数の2乗以上である整数だけ取り除いたらそれらは(1,1)一択であると考えればよい。

あとは、
g(a,c) := a,cに対しaB=cDを満たすB,Dの組み合わせ数
を求められれば、f(a,c)*g(a,c)の総和が解となる。

a,cを互いに素となるよう最大公約数で割っておく。
a≦cのケースで考えると、Dはcの倍数のみ取れる(その時BはD*c/a)。
よってまとめるとg(a,c) := N/(max(a,c)/gcd(a,c))となる。

ll mo=1000000007;
int pat[101010];
ll num[35][35];

class PowerEquation {
	public:
	int count(int n) {
		ZERO(pat);
		ZERO(num);
		int left=max(0,n-100000);
		
		
		int i,x,y;
		for(i=2;i<=min(n,100000);i++) if(pat[i]==0) {
			int mul=1;
			ll j=i;
			while(j*i<=n) {
				j*=i;
				mul++;
				if(j<=100000) pat[j]++;
				else left--;
			}
			for(x=1;x<=mul;x++) for(y=1;y<=mul;y++) num[x][y]++;
		}
		
		num[1][1]+=left;
		
		ll ret=1LL*n*n%mo;
		for(x=1;x<=34;x++) for(y=1;y<=34;y++) if(num[x][y]) {
			int g=__gcd(x,y);
			int a=max(x,y)/g;
			ret += (n/a)*num[x][y]%mo;
		}
		
		return ret%mo;
	}
}

まとめ

解けたけどちょっと手間取った。