[原创]POJ 1305 Fermat vs. Pythagoras [本源毕达哥拉斯不等式]【数论】

2016-09-21 21:39:52 Tabris_ 阅读数：300

博客爬取于2020-06-14 22:43:10
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52613712

题目链接：http://poj.org/problem?id=1305
-------------------------------.
Fermat vs. Pythagoras
Time Limit: 2000MS Memory Limit: 10000K
Total Submissions: 1561 Accepted: 913
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
----------------------------.

题目大意 ：
就是问你在小于N中选取三个元素能构成多少个本源毕达哥拉斯不等式与其中不能形成毕达哥拉斯不等式的元素有多少个

解题思路：

毕达哥拉斯不等式
x^2 + y^2 = z^2 （其实就是勾股定理）

本源毕达哥拉斯不等式就是满足gcd（x，y，z）==1时的毕格拉斯不等式；

毕达哥拉斯不等式有下列特点
x=m^2-n^2;
y=2mn;
z=m^2+n^2;

其中m+n为奇数
在本源毕达哥拉斯不等式中满足gcd(m,n)==1;

本题数据量很小 所以只需要枚举一下m，n就行了

附本题代码
----------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# include<stdio.h>
# include<string.h>
# include<stdlib.h>
# include<time.h>
# include<iostream>
# include<string.h>
# include<math.h>
# include<algorithm>
using namespace std;

typedef long long int LL ;
/**********************************/

int sum ,num;
int gcd(int a,int b)
{
    if(!b)return a;
    return gcd(b,a%b);
}
bool flag [1010101];
void solve(int t)
{
    sum=0,num=0;
    for(int i=1;i<=t;i++)flag[i]=true;
    int temp=sqrt(t*1.0);
    int x,y,z;
    for(int i=1;i<=temp;i++)
    {
        for(int j=i+1;j<=temp;j++)
        {
            if(i*i+j*j>t) break;
            if(i%2!=j%2&&gcd(i,j)==1)
            {
              x=j*j-i*i;
              y=2*i*j;
              z=i*i+j*j;
              //printf("%d %d %d\n",x,y,z);
              sum++;
              for(int k=1;k*z<=t;k++)  flag[k*x]=flag[k*y]=flag[k*z]=false;
            }
        }
    }
    for(int i=1;i<=t;i++)  if(flag[i])  num++;//,printf("%d ",i);puts("");
    printf("%d %d\n",sum,num);
}
int main()
{
    int n;
    while(~scanf("%d",&n))   solve(n);
    return 0;
}