UVA1069 Always an integer

数论思维题

1.UVA1069 Always an integer

题目翻译

给一个项数小于100的多项式，问其在任意整数下的值模D是否为0 。

题目分析

随机取若干个值，如果这些值都令多项式的取值都模D为0，那么这个多项式大概率是在模D意义下为0的。

那么考虑把值(1,2,3,4,….n+1)给带入方程，根据差分数组的性质，$f(n+1)-f(n)$为一个最高次项比f的最高次项小1的多项式，那么对于n阶的多项式计算出来n阶的差分即可变为一个常数，因为取模对于加减法有分配率，那么如果所有的差分值都模D为0，那么整个多项式无论取什么值都模D为0。那么就得出了做法。

代码

//
// Created by mrx on 2022/9/13.
//
#include <bits/stdc++.h>

using ll = long long;

ll power(ll a, ll b, ll mod) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1)ans = a * ans % mod;
    return ans;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif
    std::string s;
    int n = 0;
    while (std::cin >> s && s != ".") {
        n++;
        std::cout << "Case " << n;

        auto check = [&](std::string &str) -> bool {
            std::vector<int> a, e;
            std::string poly = str.substr(1, str.find('/') - 2);
            int ptr = 0, n = poly.size();
            while (ptr < n) {
                int sig = 1;
                //sign
                if (poly[ptr] == '+') sig = 1, ptr++;
                if (poly[ptr] == '-') sig = -1, ptr++;

                //计算系数
                int digit = 0;
                while (ptr < n && isdigit(poly[ptr])) digit = digit * 10 + poly[ptr++] - '0';
                //常数
                if (ptr == n) {
                    a.push_back(digit);
                    e.push_back(0);
                } else {
                    ptr++;
                    if (digit == 0)digit = 1;
                    digit *= sig;
                    int pw = 0;
                    if (poly[ptr] == '^') {
                        ptr++;
                        //不为1次项k
                        while (ptr < n && isdigit(poly[ptr])) pw = pw * 10 + poly[ptr++] - '0';
                    } else pw = 1;
                    a.push_back(digit);
                    e.push_back(pw);
                }
            }

            int D = stoi(str.substr(str.find('/') + 1));
//            for (int i = 0; i < a.size(); ++i)std::cerr << a[i] << '^' << e[i] << ' ';
            std::cerr << '\n';
            for (int x = 1; x <= e[0] + 1; ++x) {
                ll ans = 0;
                for (int i = 0; i < a.size(); ++i) {
                    ans = (ans + a[i] * power(x, e[i], D) % D) % D;
                }
                if (ans)return false;
            }
            return true;
        };

        if (check(s))std::cout << ": Always an integer\n";
        else std::cout << ": Not always an integer\n";
    }
    return 0;
}