SRM567 Div2 Medium "TheSquareRootDilemma"
問題
2つの整数を引数に取り、下記のような値を返すSSRという関数がある
SSR(A, B) = (sqrt(A)+sqrt(B))^2
NとMが与えられる。
1 <= A <= N、1 <= B <= Mの範囲で関数SSRが整数を返す場合の数を返せ。
制約
1 <= N <= 77777
1 <= M <= 77777
考えた事
時間内ではNとMで全探索するものしか思いつかず
forループ内でbreak使って計算量を減らそうとしたんだけどTLE・・・
まあ自分の環境で実行したら30秒ぐらいかかってたしね
SSR(A, B) = (sqrt(A)+aqrt(B))^2 = A + B + 2 * ルートABだから、
A * Bが平方数になれば、SSR(A, B)は整数になる。
例えばAを72と決めると
72 * Bが平方数になればいい。
72 = 2 * 2 * 2 * 3 * 3だから
72 * B = 2^2 * 3^2 * 2 * B = 6^2 * 2 * Bになって6^2はルートの外に出せるから、
2 * Bが平方数になればいい。
B = 2 * n * nというようなnがあれば、
2 * B = 2 * 2 * n * nとなって平方数になる!
B = 2 * n * nとなるようなnを探すにルートM回
これをN回繰り返すので、
計算量はO(NルートM)で大体2000万回
ソースコード
class TheSquareRootDilemma { public: // 2乗でくくれない余りものを返す // 72 なら 2^2 * 3^2 * 2 なので 2を返す int powMod( int x ){ for( int i = 2; i * i <= x; i++ ){ while( (x % (i*i)) == 0 ){ x /= i * i; } } return x; } int countPairs(int N, int M){ int res = 0; for( int i = 1; i <= N; i++ ){ int a = powMod( i ); for( int j = 1; j * j * a <= M; j++ ){ res++; } } return res; } }