POJ 1305 Fermat vs. Pythagoras 解原毕达哥拉斯三元组

Description

Input

Output

Sample Input

10
25
100

Sample Output

1 4
4 9
16 27

Source

//1364K	0MS
#include<stdio.h>
#include<math.h>
#include<string.h>
bool vis[1000007];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
void solve(int t)
{
    int x,y,z,m,n,tmp=sqrt(t),ans1=0,ans2=0;
    memset(vis,0,sizeof(vis));
    for(n=1;n<=tmp;n++)
    {
        for(m=n+1;m<=tmp;m++)
        {
            if(m*m+n*n>t)break;
            if(n%2!=m%2)
            {
                if(gcd(m,n)==1)
                {
                    x=m*m-n*n;
                    y=2*m*n;
                    z=m*m+n*n;
                    ans1++;
                    for(int i=1;;i++)
                    {
                        if(i*z>t)break;
                        vis[i*x]=1;
                        vis[i*y]=1;
                        vis[i*z]=1;
                    }
                }
            }
        }
    }
    for(int i=1;i<=t;i++)
        if(!vis[i])ans2++;
    printf("%d %d\n",ans1,ans2);
}
int main()
{
    int t;
    while(scanf("%d",&t)!=EOF)
    {
        solve(t);
    }
    return 0;
}