HDU 4320：Arcane Numbers——進制有限小數判定

題目描述

給定 A 進制有限小數，轉為 B 進制後是否仍為有限小數。多組測試，A,B ≤ 2×10⁹。

數學原理

A 進制有限小數 ⇔ 存在 n 使 x * Aⁿ 為整數。轉 B 進制後有限 ⇔ 存在 m 使 x * Aⁿ * Bᵐ 為整數 ⇔ A 的所有質因子都被 B 包含。

即：check(A, B) = true 當且僅當 A 的每個質因子都能整除 B。

算法

1. 分解 A 的質因子
2. 檢查每個質因子是否整除 B
3. 若 A 剩餘質因子 > 1 也需檢查

C++ 實現

#include <cstdio>
using namespace std;
typedef long long LL;

bool check(LL a, LL b) {
    for (LL i = 2; i*i <= a; ++i) {
        if (a % i == 0) {
            if (b % i) return false;
            while (a % i == 0) a /= i;
        }
    }
    if (a > 1 && b % a) return false;
    return true;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        LL a, b; scanf("%lld%lld", &a, &b);
        printf("Case #%d: %s\n", cas, check(a,b) ? "YES" : "NO");
    }
    return 0;
}

複雜度

• 單次測試：O(√A) ≈ 4.5×10⁴，T ≤ 100 極快