HDU 4282 A very hard mathematic problem：暴力枚舉求解 x^z + y^z + xyz = k

問題描述

給定 k (k < 2^31)，求正整數三元組 (x,y,z) 滿足 x^z + y^z + x*y*z = k，其中 x < y, z > 1。統計解的個數。

關鍵觀察

• z=2 時：x^2 + y^2 + 2xy = (x+y)^2 = k。故 k 必為完全平方數，設 t = sqrt(k)，則 x+y = t，滿足 xfloor((t-1)/2)。
• z≥3 時：x^z 增長極快。因 k < 2^31，x < 2^(31/3) ≈ 1290。可雙重枚舉 x,y，內層枚舉 z 直到超過 k。

演算法

1. 若 k 為完全平方數，加上 z=2 的解數。
2. 對 x=1..而 x^3 < k：
   • 對 y=x+1..而 y^3 < k：
     • 對 z=3.. 計算 x^z, y^z (快速冪，溢出剪枝)。
     • 若 x^z + y^z + x*y*z == k 計數++。
     • 若和 > k 跳出 z 循環。

複雜度

x,y 最大 ~1300，z 很小 (因指數增長)，總操作數極少，極易通過。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 INF = 0x7fffffff;

int64 ipow(int64 a, int64 e) {
    int64 r = 1;
    while (e) {
        if (e & 1) { if (r > INF / a) return -1; r *= a; }
        e >>= 1;
        if (e) { if (a > INF / a) return -1; a *= a; }
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int k;
    while (cin >> k, k) {
        int ans = 0;
        int t = (int)sqrt(k);
        if (t*t == k) ans += (t-1)/2; // z=2
        for (int64 x=1; x*x*x < k; ++x) {
            for (int64 y=x+1; y*y*y < k; ++y) {
                for (int z=3;; ++z) {
                    int64 p1 = ipow(x, z), p2 = ipow(y, z);
                    if (p1==-1 || p2==-1) break;
                    int64 sum = p1 + p2 + x*y*z;
                    if (sum == k) ++ans;
                    if (sum >= k) break;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}