SRM365 Div2 600

とぷこだ 過去問

問題

ある半径rの円上の整数点(x,y)がいくつあるか．

x^2+y^2=nのとき，その個数は4*( d_1(n)-d_3(n) )になる．d_i(n)はnの約数を4で割ったもののうちで余りがiであるものの個数．

考え方

以下の通り。
http://d.hatena.ne.jp/phyllo_algo/20101106/1289055084


■n^2の約数列挙
nを素因数分解して(a^A)*(b^B)*(c^C)*...のようになった場合、n^2は(a^2A)*(b^2B)*(c^2C)*...となるので、したがって、その約数は、
「(a^i)*(b^j)*(c^k)*...」
0<=i<=2A,
0<=j<=2B,
0<=k<=2C,...
となる。
これを求める方法として、nの約数divを求めてそれらの直積div[i]*div[j]を計算する方法と、素因数分解して上記のように列挙するか。