首页 > 数学相关 > hdu 1615 Fermat vs. Pythagoras-枚举-[解题报告]
2013
12-16

hdu 1615 Fermat vs. Pythagoras-枚举-[解题报告]

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;
}


解题转自:http://www.cnblogs.com/staginner/archive/2011/12/09/2282734.html


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