TopCoder SRM 567 Div1 Easy TheSquareRootDilemma

今回はMediumで方針を間違ってしまいEasyのみAC。
Challengeを1ミスしたこともありレートが微減してしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=12377

NとMが与えられるので、が整数になるような1<=A<=N、1<=B<=Mの組み合わせ数を答える。

との√内の数値が同じならいいので、AおよびBは平方数の倍数なら、その平方数で割り、√内に残る数が同じになる組み合わせを求めればよい。

int np;
int prime[1000];
int A[77778];
int B[77778];
const int prime_max = 1000;
void cprime() {
	int i,j;
	char p[prime_max];
	
	np=0;
	ZERO(p);
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[np++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=1;
	}
}


class TheSquareRootDilemma {
	int rot[77778];
	public:
	int countPairs(int N, int M) {
		int i,j,k;
		cprime();
		FOR(i,77778) {
			rot[i]=i;
			FOR(j,np) {
				ret:
				if(rot[i]<prime[j]*prime[j]) break;
				if((rot[i] % (prime[j]*prime[j]))==0){
					rot[i] /= prime[j]*prime[j];
					goto ret;
				}
			}
		}
		
		ZERO(A);
		ZERO(B);
		for(i=1;i<=N;i++) A[rot[i]]++;
		for(i=1;i<=M;i++) B[rot[i]]++;
		int res=0;
		for(i=1;i<=max(N,M);i++) res+=A[i]*B[i];
		return res;
	}

};

まとめ

これ、わざわざ素数を求めてるけど素数を求める必要なかったね。
合成数の二乗でもいいわけだし、それでも計算量は問題ないし。