[BZOJ1041][HAOI2008][数学乱搞]圆上的整点

[Problem Description] 求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。 [Algorithm] 数学乱搞 [Analysis] 题目倒是很简洁明了……但是有点让人无从下手 我们一步一步来分析： 首先写出式子  X ^ 2 + Y ^ 2 = R ^ 2 移项  Y ^ 2 = R ^ 2 - X ^ 2            = (R + X)(R - X) 设  d = GCD(R + X, R - X) 则  Y ^ 2 = d ^ 2 * (R + X) / d * (R - X) / d 设  A = (R + X) / d, B = (R - X) / d 则  A != B 且 GCD(A, B) = 1 且  Y ^ 2 = d ^ 2 * A * B 由于Y ^ 2 是完全平方数, d ^ 2也是完全平方数, 而A, B互质，所以A, B都是完全平方数 设  A = a ^ 2, B = b ^ 2 则  a ^ 2 + b ^ 2 = 2 * R / d 说明 d 是 2 * R 的因数，以此可以在[1, sqrt(2 * R)]的范围内枚举i，当2 * R % i == 0时，i 和 2 * R / i都是2 * R 的因数。确定 2 * R / d 的值，假设a < b，我们再在[1, sqrt((2 * R / d) / 2)]的范围内枚举a, 算出对应的 A, b, B， 如果A, B都是完全平方数而且 A != B, GCD(A, B) == 1则方案数加1。这是一个象限的方案数，最后再* 4 再加上坐标轴上的4个即可 [Pay Attention] 用long long啊用long long！ 注意以后求勾股数相关的都可以利用这里推出的结论…… [Code]

/**************************************************************
    Problem: 1041
    User: gaotianyu1350
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:1284 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
 
const long long INF = 2000000000;
long long ans = 0;
long long r;
 
long long gcd(long long a, long long b)
{
    return !b ? a : gcd(b, a % b);
}
 
void solve(long long left)
{
    long long temp = (int) sqrt(left / 2);
    for (long long a = 1; a <= temp; a++)
    {
        long long A = a * a;
        long long B = left - A;
        long long b = (int)sqrt(B);
        if (b * b == B && gcd(A, B) == 1 && A != B)
            ans++;
    }
}
 
int main()
{
    scanf("%lld", &r);
    long long tar = (int)sqrt(2 * r);
    for (long long i = 1; i <= tar; i++)
        if (2 * r % i == 0)
        {
            solve(2 * r / i);
            solve(i);
        }
    printf("%lld\n", ans * 4 + 4);
}