「Project Euler 9」特殊勾股数 题解

题目分析

题目要求

给定自然数 ( N )，找出所有满足以下条件的三元组 ( (a, b, c) )：

1. ( a, b, c ) 均为自然数；
2. ( a < b < c )；
3. ( a^2 + b^2 = c^2 )（勾股数定义）；
4. ( a + b + c = N )。

数据范围

• 20% 数据：( N \leq 5000 )
• 40% 数据：( N \leq 10^6 )
• 100% 数据：( N \leq 10^{12} )

解题思路

数学推导（核心）

从题目条件出发，通过代数变换将问题简化，避免暴力枚举：

1. 由 ( a + b + c = N ) 得 ( c = N - a - b )；
2. 将 ( c ) 代入勾股定理 ( a^2 + b^2 = c^2 )： [ a^2 + b^2 = (N - a - b)^2 ]
3. 展开右侧并化简： [ a^2 + b^2 = N^2 + a^2 + b^2 + 2ab - 2N(a + b) ] 消去 ( a^2 + b^2 ) 后整理得： [ N^2 - 2N(a + b) + 2ab = 0 ]
4. 进一步变形求解 ( b )： [ N^2 - 2Na - 2Nb + 2ab = 0 \ N^2 - 2Na = b(2N - 2a) \ b = \frac{N^2 - 2Na}{2(N - a)} ]
5. 补充约束：
   • ( a < b < c ) 可推导得 ( a < \frac{N}{3} )（因为 ( a < b < c )，所以 ( 3a < a + b + c = N )）；
   • ( b ) 必须是自然数，因此 ( N^2 - 2Na ) 必须能被 ( 2(N - a) ) 整除；
   • ( c = N - a - b ) 需满足 ( b < c ) 且为自然数。

优化枚举范围

• 暴力枚举 ( a ) 的范围是 ( [1, N/3) )，但 ( N \leq 10^{12} ) 时直接枚举不可行；
• 结合勾股数的性质：勾股数可表示为 ( a = k(m^2 - n^2) )、( b = 2kmn )、( c = k(m^2 + n^2) )（其中 ( m > n > 0 )，( m,n ) 互质且奇偶性不同，( k ) 为正整数）；
• 代入 ( a + b + c = N ) 得：( 2km(m + n) = N )，因此只需枚举 ( N ) 的因数，再验证是否满足勾股数条件。

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long  // 处理 1e12 范围的大数

int N;
vector<int> factors;  // 存储 N 的所有因数
vector<pair<int, int>> prime_factors;  // 质因数分解结果 (质数, 指数)

// 快速幂（无实际使用，保留以兼容原代码）
int pw(int a, int b, int p) {
    int res = 1;
    int y = a % p;
    while (b) {
        if (b & 1)
            res = res * y % p;
        y = y * y % p;
        b >>= 1;
    }
    return res;
}

// 质因数分解
void prime_factorize(int n) {
    prime_factors.clear();
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            prime_factors.emplace_back(i, cnt);
        }
    }
    if (n > 1)
        prime_factors.emplace_back(n, 1);
}

// 深度优先搜索生成所有因数
void dfs(int idx, int now) {
    if (idx == prime_factors.size()) {
        factors.push_back(now);
        return;
    }
    int p = prime_factors[idx].first;
    int exp = prime_factors[idx].second;
    int mul = 1;
    for (int i = 0; i <= exp; ++i) {
        dfs(idx + 1, now * mul);
        mul *= p;
    }
}

// 生成所有因数
void get_all_factors() {
    factors.clear();
    prime_factorize(N);
    dfs(0, 1);
    sort(factors.begin(), factors.end());
}

// 验证并输出符合条件的勾股数
void find_pythagorean_triples() {
    vector<tuple<int, int, int>> res;  // 存储结果，便于排序输出
    get_all_factors();

    // 枚举 a 的可能值（基于数学推导的优化）
    for (int a : factors) {
        if (a * 3 >= N) break;  // a < N/3
        if (a == 0) continue;

        __int128 numerator = (__int128)N * N - 2 * (__int128)N * a;
        __int128 denominator = 2 * ((__int128)N - a);

        if (numerator % denominator != 0) continue;
        int b = (int)(numerator / denominator);
        int c = N - a - b;

        // 验证所有条件
        if (b <= a || c <= b) continue;
        if ((__int128)a * a + (__int128)b * b != (__int128)c * c) continue;

        res.emplace_back(a, b, c);
    }

    // 按 a 升序输出
    sort(res.begin(), res.end());
    for (auto [a, b, c] : res) {
        cout << a << " " << b << " " << c << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    find_pythagorean_triples();

    return 0;
}

代码解释

核心模块

1. 质因数分解：

   • prime_factorize 函数将 ( N ) 分解为质因数的乘积（如 ( 120 = 2^3 \times 3^1 \times 5^1 )）；
   • 目的是生成 ( N ) 的所有因数，减少枚举范围。

2. 因数生成：

   • dfs 函数通过深度优先搜索，基于质因数分解结果生成所有因数；
   • 枚举因数而非直接枚举 ( a )，将时间复杂度从 ( O(N) ) 降至 ( O(\sqrt{N}) )（质因数分解） + ( O(d(N)) )（因数个数，( d(N) ) 远小于 ( N )）。

3. 验证条件：

   • 使用 __int128 避免大数运算溢出（如 ( a^2 ) 当 ( a=1e12 ) 时，普通 long long 会溢出）；
   • 验证 ( a < b < c ) 和勾股定理，确保结果正确。

复杂度分析

• 时间复杂度：
  • 质因数分解：( O(\sqrt{N}) )；
  • 生成因数：( O(d(N)) )（( d(N) ) 为 ( N ) 的因数个数，对于 ( N \leq 10^{12} )，( d(N) ) 最大约为 1000）；
  • 总复杂度：( O(\sqrt{N} + d(N)) )，可轻松处理 ( 10^{12} ) 范围的 ( N )。
• 空间复杂度：( O(d(N)) )，主要用于存储因数和结果。

测试样例验证

样例 1

输入：12

• 因数枚举 ( a ) 的可能值：1, 2, 3, 4, 6, 12；
• 筛选后 ( a=3 )：
  • ( b = (12^2 - 2123)/(2*(12-3)) = (144-72)/18 = 4 )；
  • ( c = 12-3-4=5 )；
  • 验证：( 3^2+4^2=5^2 )，且 ( 3<4<5 )，输出 3 4 5。

样例 2

输入：120

• 枚举因数后得到三个符合条件的三元组：
  1. ( a=20 )，( b=48 )，( c=52 )；
  2. ( a=24 )，( b=45 )，( c=51 )；
  3. ( a=30 )，( b=40 )，( c=50 )；
• 排序后输出结果与样例一致。

注意事项

1. 大数溢出：必须使用 long long 或 __int128 处理大数，避免运算溢出；
2. 枚举范围：严格限制 ( a < N/3 )，减少无效枚举；
3. 结果排序：按 ( a ) 升序输出，保证结果格式统一；
4. 边界条件：排除 ( a=0 ) 或 ( b \leq a ) 等无效情况。

总结

本题的核心是通过数学推导将问题转化为因数枚举，避免暴力枚举，结合质因数分解和大数运算优化，高效解决 ( N \leq 10^{12} ) 的情况。掌握勾股数的数学性质和因数分解技巧，是解决此类数论问题的关键。