読者です 読者をやめる 読者になる 読者になる

SRM 567 Div1

○-- +1/-0 283位 rating : 1335 -> 1467
easy出してうなっとしていたら腹痛で死んでそのまま終わりました。easy提出遅すぎなんだよね。

easy
(sqrt(a) + sqrt(b)) ^ 2 = a + b + sqrt(ab)なので、abが平方数だと良くて、
a, bが共に平方数×kとかになればいいので、適当に数える。ダブらないように比率みたいなのをmap使って管理した(伝われー)

class TheSquareRootDilemma{
    public:
	int countPairs(int N, int M){
	    int ret = 0;
	    vector<ll> sq;
	    map<P, int> u;
	    for(ll i = 1; i * i <= 77777; i++)  sq.pb(i * i);
	    rep(i, sq.size()){
		rep(j, sq.size()){
		    if(N < sq[i] || M < sq[j]) break;
		    ll a = sq[i], b = sq[j];
		    ll d = __gcd(a, b);
		    a /= d; b /= d;
		    if(!u[P((int)a, (int)b)])ret += min((ll)N / sq[i], (ll)M / sq[j]);
		    u[P((int)a, (int)b)]++;
		}
	    }
	    return ret;
	}
};