-数论- [BZOJ 1041][HAOI2008]圆上的整点

题目描述

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

输入格式

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

输出格式

整点个数

样例输入

样例输出

Solution

主要就是这个视频：https://www.bilibili.com/video/av12131743/

视频里原理已经讲得hin明白，时间复杂度：O(分解质因数)。

~~如果不看这个视频估计谁也想不到圆竟然和质因数有关系~~

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define MAXN 50000
ll n , k , p , tot = 0 , ans = 1;
bool gauss(ll a) {
    if (a % 4 != 3) return 1;
    return 0;
}
int main() {
    scanf("%lld" , &n);
    while (!(n & 1)) n >>= 1;
    for (ll i = 2; i <= sqrt(n) ; i++) {
        p = 0;
        while (n % i == 0) {
            if (gauss(i)) p += 2;
            n /= i;
        }
        ans *= (p + 1);
    }
    if (n != 1) {
        if (gauss(n)) {
            ans *= 3;
        }
    }
    printf("%d" , ans * 4);
    return 0;
}