HNU11722 The Gougu Theorem

　　原题传送：http://acm.hnu.cn/online/?action=problem&type=show&id=11722&courseid=0

　　给出z，求符合方程x² + y² = z²的个数并输出。

　　这个问题在二潘的《初等数论》中有很详细的阐述。简单来说就是：

　　如果 z = i² + j²

　　那么

　　　　x = i² - j²

　　　　y = 2 * i * j

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef pair<int, int> pii;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    int c, cas = 1, i, j, x, y;
    vector<pii> v;
    while(scanf("%d", &c), c)
    {
        printf("Case %d:\n", cas ++);
        if(c % 4 != 1)
        {
            printf("There are 0 solution(s).\n\n");
            continue;
        }
        v.clear();
        int len = (int)sqrt(c + 0.5);
        for(i = 1; i <= len; i ++)
        {
            j = (int)sqrt(c - i * i + 0.5);
            x = j * j - i * i, y = 2 * i * j;
            if(i < j && i * i + j * j == c && gcd(x, y) == 1 && gcd(c, x) == 1 && gcd(c, y) == 1)
            {
                v.push_back(make_pair(min(j * j - i * i, 2 * i * j), max(j * j - i * i, 2 * i * j)));
            }
        }       
        sort(v.begin(), v.end());
        len = v.size();
        printf("There are %d solution(s).\n", len);
        for(int i = 0; i < len; i ++)
        {
            printf("%d^2 + %d^2 = %d^2\n", v[i].first, v[i].second, c);
        }
        putchar('\n');
    }
    return 0;
}