ZeroJudge 解題筆記：c098. 00106 - Fermat vs. Pythagoras

作者：王一哲
日期：2026年3月3日


ZeroJudge 題目連結：c098. 00106 - Fermat vs. Pythagoras

解題想法

這題困難之處在於找數學關係，不能用暴力法跑兩層迴圈，一定會超時。 畢氏三元組 (Pythagorean triples) 的定義為滿足 $x^2 + y^2 = z^2$ 的正整數為 $(x, y, z)$。原始畢氏三元組 (Primitive Pythagorean triples) 還要再加上 $x, y, z$ 互質的條件，也就是 $gcd(x, y, z) = 1$。需要用到的性質為 $$ x = m^2 - n^2, ~~~ y = 2mn, ~~~ z = m^2 + n^2 $$ 其中

• $m > n> 0$，且 $m, n$ 為整數。
• $m, n$ 互質，即 $gcd(m, n) = 1$
• $m - n$ 為奇數，即 $m, n$ 為一個奇數、一個偶數。

推導過程

直角三角形邊長 $x^2 + y^2 = z^2$，其中 $z$ 是斜邊。因為 $(x, y, z)$ 互質，不可能有 2 個以上的偶數，所以

• $x, z$ 是奇數
• $y$ 是偶數

假設 $y \equiv 2k$，其中 $k$ 為正整數，則 $$ x^2 + (2k)^2 = z^2 ~\Rightarrow~ x^2 + 4k^2 = z^2 ~\Rightarrow~ z^2 - x^2 = 4k^2 ~\Rightarrow~ (z+x)(z-x) = 4k^2 $$ 假設 $a = z-x, ~b = z+x$，因為 $z, x$ 是奇數，所以 $a, b$ 是偶數。假設 $a = 2p, ~b = 2q$，則 $$ 2p \cdot 2q = (2k)^2 ~\Rightarrow~ pq = k^2 $$ 因為 $x, z$ 互質，所以 $p, q$ 互質，為了符合 $pq = k^2$，$p, q$ 必須是平方數。 假設 $p = n^2,~ q = m^2$，由於 $$ a = z-x = 2p = 2n^2, ~~~ b = z+x = 2q = 2m^2 $$ 由 $a+b$ 可以解 $z$ $$ a+b = 2z ~\Rightarrow~ 2(m^2 + n^2) = 2z ~\Rightarrow~ z = m^2 + n^2 $$ $$ x = z - a = m^2 + n^2 - 2n^2 = m^2 - n^2 $$ $$ y = \sqrt{z^2 - x^2} = \sqrt{(m^2 + n^2)^2 - (m^2 - n^2)^2} = \sqrt{4m^2 n^2} = 2mn $$

Python 程式碼

使用時間約為 0.4 s，記憶體約為 60.5 MB，通過測試。

import sys, math

def solve(maxn):
    status = [False]*(maxn+1)  # 0 ~ maxn 是否為畢氏三元組
    coprime = [0]*(maxn+1)  # 0 ~ maxn 互質三元組數量前綴和
    """
     計算 0 ~ maxn 之間的原始畢氏三元組與所有畢氏三元組數量
     依序檢查 m = 2 ~ sqrt(maxn), n = 1 ~ m-1
     如果 m-n 是奇數，m, n 互質，則 x = m^2 - n^2, y = 2mn, z = m^2 + n^2
     為原始畢氏三元組，再將 (x, y, z) 乘以整數倍，找其它的畢氏三元組
    """
    for m in range(2, int(maxn**0.5) + 1):
        for n in range(1, m):
            if (m-n)%2 == 1 and math.gcd(m, n) == 1:
                x, y, z = m*m - n*n, 2*m*n, m*m + n*n
                if z > maxn: continue  # z 超過上限，找下一組
                coprime[z] += 1  # z 對應的原始畢氏三元組數量加 1
                k = 1  # 原始畢氏三元組的 k 倍，如果 k > 1 為不互質的三元組
                while k*z <= maxn:  # 如果 k*z 還沒有超過上限繼續執行
                    status[k*x], status[k*y], status[k*z] = True, True, True
                    k += 1
    # coprime 改成前綴和
    for i in range(1, maxn+1):
        coprime[i] += coprime[i-1]
    # 0 ~ maxn 之間非畢氏三元組的數量前綴和
    non_member = [0]*(maxn+1)
    cnt = 0
    for i in range(1, maxn+1):
        if not status[i]: cnt += 1
        non_member[i] = cnt
    sys.stdout.write(f"{coprime[maxn]:d} {non_member[maxn]:d}\n")

for line in sys.stdin:
    solve(int(line))

C++ 程式碼

使用時間約為 14 ms，記憶體約為 8 MB，通過測試。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

void solve(int maxn) {
    vector<bool> status (maxn+1, false);  // 0 ~ maxn 是否為畢氏三元組
    vector<int> coprime (maxn+1, 0);  // 0 ~ maxn 互質三元組數量前綴和
    /* 計算 0 ~ maxn 之間的原始畢氏三元組與所有畢氏三元組數量               *
     * 依序檢查 m = 2 ~ sqrt(maxn), n = 1 ~ m-1                             *
     * 如果 m-n 是奇數，m, n 互質，則 x = m^2 - n^2, y = 2mn, z = m^2 + n^2 *
     * 為原始畢氏三元組，再將 (x, y, z) 乘以整數倍，找其它的畢氏三元組      */
    for(int m=2; m<=(int)sqrt(maxn); m++) {
        for(int n=1; n<m; n++) {
            if ((m-n)%2 == 1 && __gcd(m, n) == 1) {
                int x = m*m - n*n, y = 2*m*n, z = m*m + n*n;
                if (z > maxn) continue;  // z 超過上限，找下一組
                coprime[z]++;  // z 對應的原始畢氏三元組數量加 1
                int k = 1;  // 原始畢氏三元組的 k 倍，如果 k > 1 為不互質的三元組
                while(k*z <= maxn) {  // 如果 k*z 還沒有超過上限繼續執行
                    status[k*x] = true; status[k*y] = true; status[k*z] = true;
                    k++;
                }
            }
        }
    }
    // coprime 改成前綴和
    for(int i=1; i<=maxn; i++) coprime[i] += coprime[i-1];
    // 0 ~ maxn 之間非畢氏三元組的數量前綴和
    vector<int> non_member (maxn+1, 0);
    int cnt = 0;
    for(int i=1; i<=maxn; i++) {
        if (!status[i]) cnt++;
        non_member[i] = cnt;
    }
    printf("%d %d\n", coprime[maxn], non_member[maxn]);
}

int main() {
    int maxn;
    while(scanf("%d", &maxn) != EOF) solve(maxn);
    return 0;
}