Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 3175
Solved 1405

Description

求一个给定的圆 (x2+y2=r^2), 在圆周上有多少个点的坐标是整数.

Input

只有一个正整数 n, n<=2000 000 000

Output

整点个数

Sample Input

4

Sample Output

4

HINT

Source

带优化的一个 sqrt () 检查...... 其实直接想一想就可以出来时间复杂度了, 大概在 O (sqrt (n)) 左右, 但是最开始我是想错了的, 以为需要 O (n^2) 才能解出来.

不多说, 直接上代码.


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long ll;
typedef double lf;

ll  z;
ll  res = 0;

ll  gcd(ll x, ll y)
{
    if (y == 0) return x;
    return gcd(y, x % y);
}

ll  sqrt_invocation(ll x)
{
    ll y = sqrt(x);
    return y * y == x ? y : -1;
}

void check(ll a, ll b)
{
    if (b <= 0) return ;
    if (gcd(a, b) == 1 && a != b)
        res++;
    return ;
}

int main(int argc, char** argv)
{
    scanf("%lld", &z);
    // Let x^2 + y^2 = z^2.
    lf  sqrt_2z = sqrt(lf(2 * z));
    for (ll p = 1; p <= sqrt_2z; p++)
        if ((2 * z) % p == 0) {
            ll  sqrt_2z_2p = sqrt(lf(z) / p); // = 2z / 2p
            for (ll a = 1; a <= sqrt_2z_2p; a++) {
                ll b = sqrt_invocation(2 * z / p - a * a);
                check(a, b);
            }
            if (p * p != 2 * z) {
                ll sqrt_p_2 = sqrt(lf(p) / 2);
                for (ll a = 1; a <= sqrt_p_2; a++) {
                    ll b = sqrt_invocation(p - a * a);
                    check(a, b);
                }
            }
        }
    printf("%lld\n", res * 4 + 4);
    return 0;
}
from pydatagen import *
r = randrange(100, 2 * 10**9)
printf('%d\n' % r)