2013
12-16

# Fermat vs. Pythagoras

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 for n > 2.

Given a positive integer N, you are to write a program that computes two quantities regarding the solution of

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).

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.

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.

10
25
100

1 4
4 9
16 27

UVA_106

继续积累数学知识，这个题目需要用到勾股数的产生公式a=m^2-n^2，b=2*m*n，c=m^2+n^2，枚举m和n就可以求出所有<=N的互质的勾股数，然后把他们的<=N的倍数都删去，剩下的数就是不属于任何一组<=N的勾股数的数字。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXD 1000010
int N, f[MAXD];
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
void solve()
{
int i, j, k, limit, num[2] = {0}, a, b, c;
for(i = 0; i <= N; i ++)
f[i] = 1;
limit = (int)sqrt(N + 1);
for(i = 1; i <= limit; i ++)
for(j = i + 1; j <= limit; j ++)
{
c = i * i + j * j;
if(c > N)
break;
a = j * j - i * i;
b = 2 * i * j;
if(gcd(gcd(a, b), c) == 1)
{
f[a] = f[b] = f[c] = 0;
num[0] ++;
for(k = 2; k * c <= N; k ++)
f[a * k] = f[b * k] = f[c * k] = 0;
}
}
for(i = 1; i <= N; i ++)
if(f[i])
num[1] ++;
printf("%d %d\n", num[0], num[1]);
}
int main()
{
while(scanf("%d", &N) == 1)
{
solve();
}
return 0;
}

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.