UVA 10375 驗證分數化簡（唯一分解定理應用）

UVA 10375 - 唯一分解定理應用：分數化簡驗證

利用算術基本定理（唯一分解定理）：任意整數 > 1 可唯一分解為質因子乘積。將分子分母分解為質因子指數向量，相減判斷是否為整數。

核心思想

對於分數 E = (X₁×X₃×...×Xₖ) / X₂：

1. 分子所有數分解質因子，指數累加
2. 分母分解質因子，指數累減
3. 若所有質因子指數 ≥ 0，則為整數

組合數計算：C(p,q)/C(r,s)

C(p,q)/C(r,s) = [p! × s! × (r-s)!] / [q! × (p-q)! × r!]
分子質因子指數 +1，分母 -1
最後正指數相乘，負指數相除（邊乘邊除防溢出）
保留 5 位小數輸出

質因子分解預處理

const int MAXN = 10005;
int prime[MAXN], pn;
bool vis[MAXN];

void sieve(int n) {
    int m = sqrt(n);
    for (int i = 2; i <= m; i++)
        if (!vis[i])
            for (int j = i*i; j <= n; j += i)
                vis[j] = 1;
    for (int i = 2; i <= n; i++)
        if (!vis[i]) prime[pn++] = i;
}

// n! 的質因子指數加 d (d=+1 或 -1)
void add_factorial(int n, int d) {
    for (int i = 0; i < pn && prime[i] <= n; i++) {
        int p = prime[i], cnt = 0;
        for (int m = n; m; m /= p) cnt += m / p;
        exp[p] += cnt * d;
    }
}

完整計算流程

// C(p,q)/C(r,s)
memset(exp, 0, sizeof(exp));
add_factorial(p, 1); add_factorial(q, -1); add_factorial(p-q, -1);
add_factorial(r, -1); add_factorial(s, 1); add_factorial(r-s, 1);

double ans = 1;
for (int i = 0; i < pn; i++) {
    if (exp[prime[i]] > 0)
        for (int j = 0; j < exp[prime[i]]; j++) ans *= prime[i];
    else if (exp[prime[i]] < 0)
        for (int j = 0; j < -exp[prime[i]]; j++) ans /= prime[i];
}
printf("%.5f\n", ans);

關鍵優化

• 質因子指數計算用 n/p + n/p² + ... 公式，O(log_p n)
• 邊乘邊除避免中間結果溢出
• 預計算質數表，多測試用例複用

複雜度分析

• 篩法：O(N log log N)
• 單次查詢：O(質數個數 × log N) ≈ 1229 × 14 ≪ 1ms