HDU 4497 GCD and LCM (組合數學視角) 詳細題解

題目連結

HDU 4497 GCD and LCM

題目大意

給定三個正整數的最大公約數 G 和最小公倍數 L，求滿足條件的有序三元組 (x, y, z) 的個數。

解題思路：從質因子指數分配角度

1. 標準化轉換

設 x = G·a, y = G·b, z = G·c，則：

• gcd(a, b, c) = 1
• lcm(a, b, c) = L / G = K

若 L 不能被 G 整除，直接輸出 0。

2. 質因子分解與獨立性

將 K 分解為質因子：K = ∏ p_i^{e_i}。
對於每個質因子 p_i，它在 a, b, c 中的指數分別為 α_i, β_i, γ_i，滿足：

• max(α_i, β_i, γ_i) = e_i (保證 lcm 含最高次方)
• min(α_i, β_i, γ_i) = 0 (保證 gcd 不含該質因子)
• 0 ≤ α_i, β_i, γ_i ≤ e_i

不同質因子之間相互獨立，總方案數為各質因子方案數的乘積。

3. 單一質因子方案數推導 (關鍵步驟)

固定指數上限 e = e_i (≥1)，求三元組 (α, β, γ) 滿足 max=e, min=0 的個數。
分類討論：

1. 恰好一個數的指數為 e：
   • 選位置：C(3,1) = 3 種。
   • 剩餘兩個數，至少一個為 0，另一個在 [0, e-1]。
     總方案：(e+1)^2 - e^2 = 2e+1 (全部組合減去都不為 0 的組合)。
     但這包含了「兩個都為 0」的情況，屬於下一類，需扣除。
     更清晰的分類：
2. 恰好兩個數的指數為 e：
   • 選位置：C(3,2) = 3 種。
   • 剩餘一個數必須為 0 (否則 min>0) → 1 種。
     共 3 × 1 = 3 種。
3. 三個數指數皆為 e：
   • 違反 min=0，0 種。

綜合「恰好一個 e」的情況：
選 1 個位置放 e (3 種)，剩 2 個位置分配 {0, 1, ..., e-1} 且至少一個為 0。
兩數從 e 個值中取值 (允許重複) 總共 e^2 種，減去都不為 0 的 (e-1)^2 種 → e^2 - (e-1)^2 = 2e-1 種。
所以「恰好一個 e」方案數 = 3 × (2e-1) = 6e - 3。
加上「恰好兩個 e」的 3 種 → 總計 (6e-3) + 3 = 6e。
結論：單一質因子方案數 = 6e。

4. 總方案數公式

Ans = ∏ (6 * e_i)，其中 e_i 為 K = L/G 的質因子分解指數。
若 K=1 (即 L=G)，空乘積為 1，唯一解 (G,G,G)。

演算法實作要點

• 試除法分解 K，複雜度 O(√K)。
• 使用 64 位整數 (long long) 儲存答案，防止溢位。
• 注意 K 分解後若 >1，說明剩一個大質因子，指數為 1，乘以 6。

C++ 參考程式碼 (含詳細註解)

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

int64 solve(int64 G, int64 L) {
    if (L % G != 0) return 0;
    int64 K = L / G;
    int64 ans = 1;
    // 試除法分解 K
    for (int64 p = 2; p * p <= K; ++p) {
        if (K % p == 0) {
            int cnt = 0;
            while (K % p == 0) {
                K /= p;
                ++cnt;
            }
            ans *= 6 * cnt; // 每個質因子貢獻 6 * 指數
        }
    }
    if (K > 1) ans *= 6; // 剩餘大質因子，指數 1
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int64 G, L;
        cin >> G >> L;
        cout << solve(G, L) << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(T * √(L/G))，對 L/G ≤ 10^9 極快。
• 空間：O(1)。

測試樣例

輸入：
3
6 72
2 4
5 5

輸出：
72
6
1

解析：
1) G=6, L=72 → K=12=2^2*3^1 → (6*2)*(6*1)=12*6=72
2) G=2, L=4 → K=2=2^1 → 6*1=6
3) G=5, L=5 → K=1 → 1

常見錯誤避坑

1. 忘記判斷 L % G != 0 直接分解導致錯誤。
2. 用 int 存儲答案導致溢位 (答案可能達 6^9 ≈ 10^7 量級，但乘積可能更大，必須用 long long)。
3. 試除法上限寫死 sqrt(K) 而不動態更新，導致遺漏大質因子或多餘迴圈。
4. 誤以為方案數為 6^e 或其他公式，未正確推導 6e。

總結

本題展示了數論中「質因子指數獨立分配」的經典思想：將 gcd/lcm 條件轉化為每個質因子指數的 max/min 限制，再利用組合計數求單因子方案數，最後乘積得總解。代碼極其簡潔，是 ACM 入門數論的優秀範例。