SRM 567 Div1 250 TheSquareRootDilemma

2013-01-21

00:00 |

1≦A≦N, 1≦B≦M に対して (√A+√B)^2 が整数になるような (A, B) の個数を求める。
N, M ≦77777

(√A+√B)^2 == A+B+2√A√B なので √A√B が整数ならいい
p0, p1, ... を素数として
A == p0^ap[0] * p1^ap[1] * ...
B == p0^bp[0] * p1^bp[1] * ...
として、各指数の偶奇が一致していればいい (ap[i]%1 == bp[i]%1 for all i)

√77777 == 278.8.. だし 290 までの素数の係数を記録すればいいか　（→まちがい
B それぞれについて偶奇を ll に詰め込んでその値から個数への map を作っておいて
A それぞれについて B の map を引いたものの個数を足してけばいい

→ failed system test

割ってく素数の最大値は 277 でいいけど、素因数自体は普通に 290 より大きなのがあるじゃんか　（よわい
ll に詰め込んだ偶奇ビットに加えて 290 以下の素数で割った後の数（1 or 大きな素数）も記録するようにしたところ OK

↓あとで (accepted in practice)

VI make_primes(int N) { // return all prime numbers less than N  memory: O(N) time: O(N^2)?
	VI p(N, 1), out;
	for(int i=2;i<N;i++) if(p[i]) { out.push_back(i); for(int j=i*2;j<N;j+=i) p[j]=0; }
	return out;
}

VI primes;
pair<ll, ll> f(int n) {
	ll out = 0LL;
	REP(ii, primes.size()) {
		int i=primes.size()-1-ii;
		int odd = 0;
		while(n % primes[i] == 0) {
			n/=primes[i];
			odd = 1 - odd;
		}
		out = (out << 1) | odd;
	}
	return MP(n, out);
}

class TheSquareRootDilemma {
	public:
	int countPairs(int N, int M) {
		primes = make_primes(290);
		
		map<pair<ll, ll>, ll> ms;
		RANGE(i, 1, M+1) {
			ms[f(i)]++;
		}
		ll ans = 0;
		RANGE(i, 1, N+1) {
			ans += ms[f(i)];
		}
		return ans;
	}
};