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