您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 4497 GCD and LCM：三數組計數的質因數分解解法

編輯：C++ 入門

題目大意

給定三個正整數的最大公約數 G 與最小公倍數 L，求有多少組有序三元組 (x, y, z) 滿足：

gcd(x, y, z) = G 且 lcm(x, y, z) = L

若無解輸出 0。多組測資，G, L ≤ 10^9 (實際測資範圍)。

數學推導核心

1. 必要條件：L 必須能被 G 整除

設 x = G·a, y = G·b, z = G·c，則 gcd(a,b,c)=1，lcm(a,b,c) = L/G = K。
若 L % G != 0，直接輸出 0。

2. 質因數分解轉化

對 K = L/G 做質因數分解：K = p1^e1 * p2^e2 * ... * pk^ek。
因 gcd(a,b,c)=1，每個質因子 pi 在 a,b,c 中的指數分佈必須滿足：

三個數中 至少有一個 指數為 ei (保證 lcm 含 pi^ei)。
三個數中 至少有一個 指數為 0 (保證 gcd 不含 pi)。
其餘數的指數可在 [0, ei] 任意選取。

3. 單一質因子的分配方案數

對指數上限 e (≥1)，三個數的指數三元組 (α, β, γ) 滿足：
max(α,β,γ)=e 且 min(α,β,γ)=0。

組合計算得：方案數 = 6e。
推導：

選 1 個位置放 e：C(3,1)=3 種。
剩 2 個位置，選 1 個放 0：C(2,1)=2 種。
最後 1 個位置可選 1..e-1 共 e-1 種，加上 0 (但 0 已在步驟2計過，避免重複) → 實際上直接推導得 6e。

4. 總方案數

各質因子分配獨立，總方案數為乘積：

Ans = ∏ (6 * ei)

若 K=1 (即 L=G)，空乘積視為 1，唯一解 (G,G,G)。

演算法步驟

讀入測資組數 T。
對每組 G, L：
- 若 L % G != 0 → 輸出 0，繼續下一組。
- K = L / G。
- 試除法分解 K (至 sqrt(K))，統計各質因子指數 ei。
- 若剩餘 K > 1，則為一質因子，指數 1。
- 初始 ans = 1，對每個 ei 乘以 6 * ei。
- 輸出 ans (需 64 位整數 long long)。

時間複雜度：O(T * sqrt(K))，K ≤ 10^9 完全可行。

C++ 參考程式碼

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int64 G, L;
        cin >> G >> L;
        if (L % G != 0) {
            cout << 0 << '\n';
            continue;
        }
        int64 K = L / G;
        int64 ans = 1;
        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;
            }
        }
        if (K > 1) ans *= 6; // 剩餘質因子指數為 1
        cout << ans << '\n';
    }
    return 0;
}