HNU 11722 The Gougu Theorem

HNU_11722

    由于勾股数a,b,c可以表示成a=m^2-n^2，b=2*m*n，c=m^2+n^2，因此可以枚举n找到所有可能的互素的勾股数，然后去掉其中重复的解即可。

    这个题目还可以用一个剪枝，就是如果c%4 !=1的话一定无解。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define MAXD 60000
int C, a[MAXD], b[MAXD], r[MAXD];
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x % y);
}
int cmp(const void *_p, const void *_q)
{
    int *p = (int *)_p, *q = (int *)_q;
    return a[*p] - a[*q];
}
void solve()
{
    int i, j, k, t, n, cnt, x, y;
    k = (int)sqrt(C + 0.5);
    n = 0;
    for(i = 1; i <= k; i ++)
    {
        j = (int)sqrt(C - i * i + 0.5);
        if(i < j && i * i + j * j == C)
        {
            x = j * j - i * i, y = 2 * i * j;
            if(gcd(x, y) == 1 && gcd(x, C) == 1 && gcd(y, C) == 1)
            {
                if(x > y)
                    t = x, x = y, y = t;
                a[n] = x, b[n] = y;
                    ++ n;
            }
        }
    }
    for(i = 0; i < n; i ++)
        r[i] = i;
    qsort(r, n, sizeof(r[0]), cmp);
    for(cnt = i = 0; i < n; i ++)
        if(!i || a[r[i]] != a[r[i - 1]])
            ++ cnt;
    printf("There are %d solution(s).\n", cnt);
    for(i = 0; i < n; i ++)
        if(!i || a[r[i]] != a[r[i - 1]])
            printf("%d^2 + %d^2 = %d^2\n", a[r[i]], b[r[i]], C);
}
int main()
{
    int t = 0;
    for(;;)
    {
        scanf("%d", &C);
        if(!C)
            break;
        printf("Case %d:\n", ++ t);
        if(C % 4 != 1)
            printf("There are 0 solution(s).\n");
        else
            solve();
        printf("\n");
    }
    return 0;
}