Fermat vs. Pythagoras
| Time Limit: 2000MS | Memory Limit: 10000K | |
| Total Submissions: 1493 | Accepted: 865 |
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).
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
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.
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,输出三元组(a,b,c)其中GCD（a，b，c）=1，且a²+b²=c²,以及1~n中没有在任何一个三元组中出现过的数的个数。
这道题需要知道勾股数的性质。
最最开始GCD（a,b,c）=1 ==> a,b,c两两互质，通过a²+b²=c²易证。
首先，对于一组勾股数，①a与b的奇偶性不同，②c一定为奇数。
证明①：若a与b同为偶数，则c也为偶数，与GCD（a，b，c）=1矛盾；若a与b同为奇数，c一定为偶数，设a=2*i+1，b=2*j+1，c=2*k -> a²+b²=c²->2*i²+2*i+2*j²+2*j+1=2*k²,这个式子是矛盾的。
证明②：a，b一奇一偶，显然。
然后将 a²+b²=c² 变形，b为偶数时，a²=(c+b)*(c-b),容易发现c-b与c+b互质，所以c-b与c+b都是平方数，设x²=c-b，y²=c+b，得a=x*y，b=(y²-x²)/2,c=(y²+x²)/2.
易得x，y都为奇数,直接枚举x，y就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=;
bool vis[maxn];
long long Gcd(long long a,long long b){
return b?Gcd(b,a%b):a;
}
int main(){
int n,m,ans,tot;
while(~scanf("%d",&n)){
m=(int)sqrt(n+0.5);ans=tot=;
memset(vis,,sizeof(vis));
for(int t=;t<=m;t+=)
for(int s=t+;(s*s+t*t)/<=n;s+=)
if(Gcd(s,t)==){
int a=s*t;
int b=(s*s-t*t)/;
int c=(s*s+t*t)/
ans++;
for(int k=;k*c<=n;k++){
vis[k*a]=true;
vis[k*b]=true;
vis[k*c]=true;
}
}
for(int i=;i<=n;i++)
if(!vis[i])
tot++;
printf("%d %d\n",ans,tot);
}
}