SRM 626 Hard

k

o

r

e

h

a

k

u

u

h

a

k

u

本質部分は、1~Kのうち、gcd(x, K)=1なるxの二乗和。(K <= 1,000,000,000)

Kの素因数を列挙して適当に包除すれば良い。