题意:给定一个多项式,推断是否总是整数
思路:LRJ大白上的例题,上面给出了证明,仅仅要1到k + 1(k为最高次数)带入方程都是整数,那么整个方程就是整数,处理出字符串后,然后过程用高速幂计算,推断最后答案是否为0,看是否全都满足是整数。
代码:
#include#include #include 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;}