POJ 1305-Fermat vs. Pythagoras（本原的毕达哥拉斯三元组+枚举）

短命女 2022-09-25 00:29 144阅读 0赞

Fermat vs. Pythagoras

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;1555</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;908</td> 
  </tr> 
 </tbody> 
</table>

Description

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level.  
This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions of a^n + b^n = c^n for n > 2.  
Given a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 = z^2, where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x < y < z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values 0 < p <= N such that p is not part of any triple (not just relatively prime triples).

Input

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file

Output

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <=N). The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N. There should be one output line for each input line.

Sample Input

10
    25
    100

Sample Output

1 4
    4 9
    16 27

Source

[Duke Internet Programming Contest 1991][],UVA 106

## 题目意思： ##

给出一个数N，求出所有小于N的X，Y，Z，使之满足X^2+Y^2=Z^2。

输出满足条件的三元组的个数，以及小于N的范围内三元组不涉及的数的个数。

## 解题思路： ##

枚举，且根据定义，本原毕达哥拉斯三元组满足：

X=m^2-n^2；

Y=2\*m\*n;

Z=m^2+n^2.

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #define MAXN 1000010
    typedef long long ll;
    using namespace std;
    
    int gcd(int a,int b)
    {
        return b==0?a:gcd(b,a%b);
    }
    void solve(int t)
    {
        int temp=sqrt(t);
        int i,m,n,x,y,z,ans1=0,ans2=0;
        bool flag[MAXN];//标识是否涉及该数
        memset(flag,false,sizeof(flag));
        for(n=1; n<=temp; ++n)//枚举
            for(m=n+1; m<=temp; ++m)
            {
                if(m*m+n*n>t) break;
                if(m%2!=n%2)
                    if(gcd(m,n)==1)
                    {
                        x=m*m-n*n;//求出三元组
                        y=2*m*n;
                        z=m*m+n*n;
                        ++ans1;
                        //cout<<x<<" "<<y<<" "<<z<<endl;
                        for(i=1;; ++i)//满足条件的三元组的整数倍也满足
                        {
                            if(i*z>t) break;
                            flag[i*x]=true;
                            flag[i*y]=true;
                            flag[i*z]=true;
                        }
                    }
            }
        for(i=1; i<=t; ++i)
            if(!flag[i])
                ++ans2;
        cout<<ans1<<" "<<ans2<<endl;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;
        while(cin>>n)
        {
            solve(n);
        }
        return 0;
    }
    
    /**
    10
    25
    100
    **/

[Duke Internet Programming Contest 1991]: http://poj.org/searchproblem?field=source&key=Duke+Internet+Programming+Contest+1991