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

NYOJ 476 誰是英雄：唯一分解定理求約數個數末位

編輯：關於C++

問題描述

10 個數學家編號 0-9，各寫一整數 aᵢ (1≤aᵢ≤10000)。計算 N = (a₁×a₂×...×a₁₀) 的約數個數。英雄編號 = N 的個位數字。輸出該數字。

數學原理：約數個數公式

若 N = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ（質因子分解），則約數個數
d(N) = (e₁+1)(e₂+1)...(eₖ+1)。
只需各質因數指數之和，不需求出巨大的 N。

算法流程

預處理 10000 以內質數（埃氏篩）。
對每個 aᵢ 分解質因子，累加指數到 cnt[p]。
計算 ans = 1; for each p: ans = ans * (cnt[p] + 1) % 10（只需個位，可全程模 10，但注意乘法模 10 可能信息丟失？實際 (e+1) 可能較大，但最終只需個位，直接用 long long 算完再取模 10 更保險，因指數和 ≤ 10×log₂10000 ≈ 130，乘積極大，但 C++ long long 可存下？10 個數各 10000，最大約數個數約 (130)^10 ≈ 1e20 超過 64 位。故逐步模 10是正確的：因只需最終個位，乘法模 10 等價於最終模 10）。
輸出 ans % 10。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXA = 10000;
vector primes;
bool is_composite[MAXA+1];
void sieve() {
    for (int i = 2; i <= MAXA; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > MAXA) break;
            is_composite[i*p] = true;
            if (i % p == 0) break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    int T; cin >> T;
    while (T--) {
        unordered_map cnt;
        for (int i = 0; i < 10; ++i) {
            int x; cin >> x;
            for (int p : primes) {
                if (p * p > x) break;
                while (x % p == 0) {
                    cnt[p]++;
                    x /= p;
                }
            }
            if (x > 1) cnt[x]++;
        }
        int ans = 1;
        for (auto [p, e] : cnt) {
            ans = (ans * (e + 1)) % 10;
        }
        cout << ans << '\n';
    }
    return 0;
}