ピタゴラス数の列挙

a^2 + b^2 = c^2
を満たす正の整数(a, b, c)をPythagorean tripleと言う。

Pythagorean tripeを列挙するには、以下のユークリッドの公式を使うといい。

すべてのPythagorean tripleは正の整数n, m, kを用いて、

a = m^2 - n^2
b = 2 m n
c = m^2 + n^2

のように一意に表すことが出来る。ただし、m, nは
m > n,
(m, n) = 1,
m != n (mod 2)
を満たす。

証明はここのProof of Euclid's formulaが分かりやすい。

これを使って以下の問題を解いてみる。

三辺の長さの合計が1,000,000以下となるような直角三角系は何個存在するか？
ただし、すべての辺の長さは整数である。

a + b + c <= 1,000,000を満たすPythagorean triple (a, b, c)の個数を求めればよい。以下のようなプログラムを書いてみた。 808950個。あってるかな？

#include <iostream>

using namespace std;

const int PERIMETER = 1e6;

long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    return gcd(b, a%b);    
}

int main(int argc, char **argv) {
    
    long long ret = 0;
    
    for (int m = 1; m * m < PERIMETER; m++) {
        for (int n = 1; n < m && n * n + m * m < PERIMETER; n++) {
            if (m % 2 == n % 2) continue;
            if (gcd(m, n) > 1) continue;

            int a = m * m - n * n;
            int b = 2 * m * n;
            int c = m * m + n * n;

            ret += PERIMETER / (a + b + c);
        }
    }

    cout << ret << endl;

    return 0;
}

おまけ：ピタゴラスの定理の証明が面白かったので、リンクを張っておく。