BZOJ 1041: [HAOI2008]圆上的整点

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

Input

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

Output

整点个数

Sample Input

4

Sample Output

4

Solution

只考虑 $x,y$ 均大于 $0$ 的情况。
首先，暴力枚举肯定是 $O(n)$ 的，T。
对于勾股数有一个结论，就是如果 $x^2+y^2=n^2$ ，那么 $x=t(a^2-b^2),y=2tab,n=t(a^2+b^2)$。
那么我们可以枚举 $t$，显然，只需要枚举 $n$ 的每个质因数是否在 $t$ 中就可以了（$t$ 中不需要有重复质因子）。
枚举 $t$ 后，需要将 $\frac n t$ 写成 $a^2+b^2$ 的形式，枚举 $a$ 从 $1$ 到 $\sqrt\frac n t)$，时间复杂度 $O(\sqrt\frac n t)$。
注意去掉重复的 $a,b$，用 map 实现即可。 总时间复杂度应该是根号乘 log 吧。。 这显然不是正解，不过跑的还是挺快的

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>

std::map<int,bool> f;

#define pmax 65536
int prime[10000],pm,x[10],y[10],cc,ans=0,n;
bool np[pmax+1];

inline int solve(int nn)
{
    int ans=0;
    for(int i=sqrt(nn);i>0;i--)
    {
        int a=nn-i*i,b=sqrt(nn-i*i);
        if(b*b==a)
        {
            int c=2*b*i,d=std::abs(b*b-i*i);
            if(!(c&&d))continue;
            if(!(f[c*(n/nn)]||f[d*(n/nn)]))
            {
                f[c*(n/nn)]=f[d*(n/nn)]=1;
                ans+=8;
            }
        }
    }
    return ans;
}

void dfs(int id,int nn)
{
    if(id==cc)
    {
        ans+=solve(n/nn);
        return;
    }
    dfs(id+1,nn);
    dfs(id+1,nn*x[id]);
}

int main()
{
    for(int i=2;i<=pmax;i++)
    {
        if(!np[i])prime[pm++]=i;
        for(int j=0;j<pm&&i*prime[j]<=pmax;j++)
        {
            np[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
    int m;
    scanf("%d",&n);
    if(n==0)
    {
        printf("1\n");
        return 0;
    }
    m=n;
    for(int i=0;i<pm;i++)
        if(n%prime[i]==0)
        {
            x[cc]=prime[i];
            while(n%prime[i]==0)n/=prime[i],y[cc]++;
            cc++;
        }
    if(n>1)x[cc++]=n;
    n=m;
    dfs(0,1);
    printf("%d\n",ans+4);
    return 0;
}

日期： 2016-09-18

标签： BZOJ 数论

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/33/ 查看。