BZOJ1041: [HAOI2008]圆上的整点 September 18, 2016 ###Description 求一个给定的圆(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后，需要将n/t写成a^2+b^2的形式，枚举a从1到sqrt(n/t)，时间复杂度O(sqrt(n/t)) 注意去掉重复的a,b，用map实现即可 总时间复杂度应该是根号乘log吧。。 <del>这显然不是正解，不过跑的还是挺快的</del> ###Code ```c++ #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; } ```