UVA 1069 Always an Integer：多項式整值性判定

問題描述

給定形如 (P(n))/D 的多項式，P 係數為整數，D 正整數。判斷對所有正整數 n 是否結果均為整數。

數學結論

設 P 最高次為 k。只需檢查 n = 1, 2, ..., k+1 時 P(n) 是否都能被 D 整除。若是，則對所有正整數成立。

解析與求值

• 解析多項式：提取各項係數 c[i] 和指數 e[i]
• 模 D 求值：pow_mod(n, e, D) 快速冪取模
• 檢查 n = 1..200（k≤100，k+1≤101，取 200 保險）

關鍵代碼

ll pow_mod(ll a, ll p, ll n) {
    ll r = 1;
    while (p) { if (p&1) r=r*a%n; a=a*a%n; p>>=1; }
    return r;
}

int main() {
    while (scanf("%s", str), str[0] != '.') {
        // 解析 str 得到 c[], e[], tot, 分母 p
        bool ok = true;
        for (int n=1; n<200; n++) {
            int tmp = 0;
            for (int j=0; j