题意：给定一个多项式，推断是否总是整数

思路：LRJ大白上的例题，上面给出了证明，仅仅要1到k + 1（k为最高次数)带入方程都是整数，那么整个方程就是整数，处理出字符串后，然后过程用高速幂计算，推断最后答案是否为0，看是否全都满足是整数。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

char str[105];

struct X {

	long long a, k;

} x[105];

long long mu, Max;

int xn;

void build() {

	mu = Max = 0; xn = 0;

	long long s = 0, a = 0, flag = 1, k = 0;

	int len = strlen(str);

	for (int i = 0; i < len; i++) {

		if (str[i] >= '0' && str[i] <= '9') {

			if (s == 0) a = a * 10 + str[i] - '0';

			if (s == 1) k = k * 10 + str[i] - '0';

			if (s == 2) mu = mu * 10 + str[i] - '0';

  		}

  		else if (str[i] == 'n')

  			s = 1;

		else if (str[i] == '/')

			s = 2;

		else if (str[i] == '+' || str[i] == '-' || str[i] == ')') {

			if (s >= 1) {

				if (a == 0) a = 1;

				if (k == 0) k = 1;

   			}

   			Max = max(Max, k);

   			x[xn].a = a * flag; x[xn].k = k; xn++;

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

   			else if (str[i] == '+') flag = 1;

   			a = k = s = 0;

  		}

 	}

}

long long pow_mod(long long x, long long k) {

	long long ans = 1;

	while (k) {

		if (k&1) ans = ans * x % mu;

  		x = x * x % mu;

  		k >>= 1;

 	}

 	return ans;

}

bool judge() {

	for (long long i = 0; i <= Max + 1; i++) {

		long long ans = 0;

  		for (int j = 0; j < xn; j++) {

			ans = (ans + x[j].a * pow_mod(i, x[j].k)) % mu;

  		}

  		if (ans) return false;

 	}

 	return true;

}

int main() {

	int cas = 0;

	while (~scanf("%s", str) && str[0] != '.') {

		build();

		printf("Case %d: %s\n", ++cas, judge()?"Always an integer":"Not always an integer");

 	}

	return 0;

}