本原毕达哥拉斯三元组是由三个正整数x,y,z组成，且gcd(x,y,z)=1,x*x+y*y=z*z
对于所有的本原毕达哥拉斯三元组（a，b，c） （a*a+b*b=c*c,a与b必定奇偶互异，且c为奇数。这里我们设b为偶数）
则：和
a=st
b=(s*s-t*t)/2
c=(s*s+t*t)/2
其中s>t>=1且gcd(s,t)=1
是一一对应的。
看看别人得证明：
看看我的证明
有了这个定理就这题就很好做了。
Fermat vs. Pythagoras
| Time Limit: 2000MS | Memory Limit: 10000K | |
| Total Submissions: 1456 | Accepted: 848 |
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
1025100
Sample Output
1 44 916 27
//// main.cpp// poj1305//// Created by 陈加寿 on 15/11/30.// Copyright (c) 2015年 陈加寿. All rights reserved.//#include#include #include #include using namespace std;int mark[1001000];long long gcd(long long a,long long b){ if(b==0) return a; return gcd(b,a%b);}int main(int argc, const char * argv[]) { int n; while(cin>>n) { memset(mark,0,sizeof(mark)); int cnt=0; for(long long i=1;;i+=2) { long long a,b,c; if( (i*i+(i+2)*(i+2))/2 >n ) break; for(long long j=i+2;;j+=2) { if(gcd(i,j)==1) { c=(i*i+j*j)/2; b=(j*j-i*i)/2; a=i*j; if(c>n) break; cnt++; for(long long k=1;k*c<=n;k++) { mark[a*k]=1; mark[b*k]=1; mark[c*k]=1; } } } } int ans=0; for(int i=1;i<=n;i++) if(mark[i]==0) ans++; cout< <<" "< <