WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
	}
}