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