题目链接：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; }