题意： 让你找出1 到 n 之间所有可以构成 x^2 +y^2 =z^2 的个数，且 x,y,z互质。

分析： 数论中有本原勾股数组的公式

x=2*s*t,y=s*s-t*t,z=s*s+t*t;

其中s>t>=1而且gcd(s,t)==1

#include
      
       #include
       
        #include
        
         int gcd(int y,int x){    return x==0?y:gcd(x,y%x);}int v[1000001];int main(){    int n,x,y,z,t1,t2,i,j,k;    while(scanf("%d",&n)!=EOF)    {        t1=t2=0;        for(i=0;i<=n;i++)            v[i]=0;        for(i=1;i*i<=n/2;i++)            for(j=i;j*j<=n;j++)            {                x=2*i*j;                y=j*j-i*i;                z=i*i+j*j;                if(z>n)break;                if(gcd(x,y)==1)                {                    t1++;                    for(k=1;k*z<=n;k++)                        v[k*x]=v[k*y]=v[k*z]=1;                }            }        for(i=1;i<=n;i++)        if(!v[i])            t2++;        printf("%d %d\n",t1,t2);    }    return 0;}