[HAOI2008]圆上的整点

数学 BZOJ

传送门

BZOJ

Solution

神仙题,本题的思路来源于视频看了之后不会被教练抓...

$x^2+y^2=R^2\Longleftrightarrow 对于平面点A(a,b),|OA|=R$

设某一个数$x$为$a+bi$.

若$x$可以分解为一对形如($a+bi$),($a-bi$)的共轭数对,那么称$x$为高斯整数

那么显然对于某一个点$(a,b)$保证$a^2+b^2=R^2$.emmm,意味着这个点是一个符合答案的点.

考虑把$R$分解一下,分解成两个复数的乘,那么两边显然是他的约数,相当于点?

所以分解质因数然后组合就可以了.

这样就没有了.

吗?

如果是一个不能够分解成两个共轭数对的数怎么办呢?$4n+3$的质数.

如果出现次数为偶数就平均分,否则就是0.

这下就没了.

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in",,"r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return f*sum;
}
int n;
int main()
{
    n=gi();ll ans=1;
    if(n==0)return puts("1"),0;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
        {
            int ps=0;
            while(n%i==0)n/=i,ps++;
            if(i%4==1)ans=1ll*ans*(2*ps+1);
        }
    if(n>1)if(n%4==1)ans=ans*3ll;
    printf("%lld\n",1ll*ans*4);
    return 0;
}