uva 1069 - Always an integer(數學+暴力)

題目鏈接：uva 1069 - Always an integer

題目大意：給出一個多次多項式，問說是否對於任意正整數n來說結構均為整數。

解題思路：首先處理出字符串，然後枚舉n從1到k+1判斷即可，k為多項式中出現過的最大冪數指。

P為多項式，d為除數，k為多項式中最大的次數

• 當k=0時，P中不存在n變量，所以直接計算判斷即可
• 當k=1時，P是一次多項式，那麼P(n+1)?P(n)=a,a為常數，也就是說P(i)為等差數列，如果首項P(1)和公差P(2)-P(1)為d的倍數即可，等價與判斷P(1)和P(2)是否為d的倍數。
• 當k=2是，P是一個k次的多項式，那麼S(n)=P(n+1)?P(n)=2an+a+b,也就是說首先是S(1)是d的倍數，並且差數列S(n)也要是d的倍數才可以，S(n)其實就是k=1的情況，需要使得S(n)的每項均為d的倍數，同樣是是首項和公差必須是d的倍數，a0=S(1)=P(2)?P(1),公差S(2)?S(1)=P(3)?P(1),等價與判斷P(1),P(2),P(3)是否為d的倍數。

#include 
#include 

typedef long long ll;
const int N = 105;
const int M = N * N;

ll c[N], d;
char str[M];

inline bool isDight (char ch) {
    return ch >= '0' && ch <= '9';
}

void init () {

    memset(c, 0, sizeof(c));

    ll k = 0, a = 0, key = 0, sign = 1;
    d = 0;

    int len  = strlen(str);
    for (int i = 0; i <= len; i++) {
        if (isDight(str[i])) {
            if (key == 0) {
                a = a * 10 + str[i] - '0';
            } else if (key == 1) {
                k = k * 10 + str[i] - '0';
            } else if (key == 2) {
                d = d * 10 + str[i] - '0';
            }

        } else if (str[i] == '/') {
            key = 2;
        } else if (str[i] == 'n') {
            key = 1;
        } else if (str[i] == '-' || str[i] == '+' || str[i] == ')') {

            if (key >= 1) {
                if (k == 0)
                    k = 1;

                if (a == 0)
                    a = 1;
            }

            c[k] = a * sign;

            if (str[i] == '-')
                sign = -1;
            else
                sign = 1;

            key = a = k = 0;
        }
    }
}

ll power(ll x, int n, ll MOD) {
    ll ans = 1;
    while (n) {
        if (n&1)
            ans = (ans * x) % MOD;
        x = (x * x) % MOD;
        n /= 2;
    }
    return ans;
}

bool judge () {
    int n = N-1;
    while (c[n] == 0)
        n--;

    /*
    for (int i = 0; i <= n; i++) {
        if (c[i])
            printf("%d %lld\n", i, c[i]);
    }
    */

    for (ll i = 1; i <= n+1; i++) {

        ll ans = 0;
        for (int j = 0; j <= n; j++) {
            if (c[j])
                ans = (ans + c[j] * power(i, j, d)) % d;
            ans = (ans + d) % d;
        }

        if (ans)
            return false;
    }

    return true;
}

int main () {
    int cas = 1;
    while (scanf("%s", str) == 1 && strcmp(".", str) != 0) {
        init();
        printf("Case %d: %s\n", cas++, judge() ? "Always an integer" : "Not always an integer");
    }
    return 0;
}