[BZOJ1041][HAOI2008]圆上的整点[数论]

[x^2+y^2=r^2 \\ y^2=left( r+x ight) left( r-x ight) \\ ext{let }d= ext{gcd}left( r+x,r-x ight) \\ ext{let }r-x=d imes a^2,r+x=d imes b^2 \\ 2r=d imes left( a^2+b^2 ight) \\ d|2r\,\,a^2ot b^2 \\ ]

用到了一个结论，两个互质的数的乘积是完全平方数,那么这两个数都是完全平方数
枚举d再枚举a

inline void solve(uint x) {
  for(uint i = 1; 2 * i * i <= x; ++i) {
    uint j = sqrt(x - i * i);
    if (j * j == x - i * i && gcd(i, j) == 1) ++ans;
  }
}
  cin >> r;r <<= 1;
  for(uint i = 1; i * i <= r; ++i) {
    if (r % i) continue;
    solve(r / i);
    if (i * i != r) solve(i);
  }
  cout << ans * 4;