SRM567 Div1 Easy - TheSquareRootDilemma

問題

整数n,mが与えられる
a,bがn,m以下かつ (√a + √b)^2が整数になるような正整数のペア(a,b)の個数を求めよ

1 <= n, m <= 77777

解法

(√a + √b)^2
= a+b + 2√ab
だからabが平方数ならok

aを全部試す
aを平方数で割れるだけ割った結果をa'とする
するとこのaとペアにできるbの条件は、b = a' * (平方数) であることになる
これはb = i * (平方数) という形で表せるm以下のbの個数をiごとに事前計算しておけばO(1)で求められる

class TheSquareRootDilemma {
public:
	int countPairs(int n, int m) {
		int b[100100] = {};
		reps(i,1,m+1) reps(j,1,1001) {
			if (j*j*i<=m) b[i]++;
			else break;
		}
		int res = 0;
		reps(i,1,n+1) {
			int a = i;
			for (int j=2; j*j<=a; j++) while (a%(j*j)==0) a /= j*j;
			res += b[a];
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12377&rd=15487