SRM365 Div1 300

とぷこだ 過去問

問題

ある半径rの円上の整数点(x,y)がいくつあるか．
x^2+y^2=nのとき，その個数は4*( d_1(n)-d_3(n) )になる．d_i(n)はnの約数を4で割ったもののうちで余りがiであるものの個数．

考え方

r*rの約数を計算しないといけない．でもr=2,000,000,000もあるので，r*rの約数をそのまま計算したらTLE．(sqrt(r*r)は約4*10^9)
「r*rの約数は，rの約数同士の直積でできる集合と同じ」になるので，それから計算する．
あとは各約数について4で割って余りが1,3となるものの個数を数えればいい．

反省

むずい．
約数の個数は，素因数分解して(x^a)*(y^b)*...となったら(a+1)*(b+1)*...となるので，そこまで約数の個数は大きくならない(はず)．