一道模拟题，题意是问一个给出的多项式代入正整数得到的值是否总是整数。
这题是一道数论题，其实对于这个式子，我们只要计算1~最高次项是否都满足即可。
做的时候，模拟出了点小错误，一直wa。幸亏最后还是能找到错误的位置。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cctype> using namespace std; const int N = ;
typedef long long LL;
char str[N]; LL powmod(LL a, LL p, LL m) {
LL ret = ;
while (p > ) {
if (p & ) ret *= a, ret %= m;
a *= a, a %= m;
p >>= ;
}
return ret;
} char *fuckbrace(char *s) {
char *p = s;
if (*p == '(') {
while (*s && *s != ')') s++;
*s = ;
p++;
}
return p;
} void scan(char *s, LL &n) {
while (*s && !isdigit(*s)) s++;
n = ;
while (*s && isdigit(*s)) n = n * + *s - '', s++;
} LL gettop(char *p) {
char *i = strstr(p, "^");
LL ret = ;
if (i) scan(i, ret);
return ret;
} LL cal(char *s, LL x, LL m) {
LL ret = , tmp = , t, p;
while (*s) {
if (isdigit(*s)) {
scan(s, t);
tmp *= t;
tmp %= m;
while (isdigit(*s)) s++;
//cout << *s << endl;
if (*s == 'n') {
LL temp = tmp;
tmp *= x;
tmp %= m;
if (*(s + ) == '^') {
scan(s + , p);
if (p == ) tmp = temp;
tmp *= powmod(x, p - , m);
tmp %= m;
s += ;
while (isdigit(*s)) s++;
} else s++;
}
ret += tmp;
ret %= m;
tmp = ;
} else if (*s == '-') {
tmp *= -;
s++;
} else if (*s == '+') s++;
else if (*s == 'n') {
//cout << "is n??" << endl;
LL temp = tmp;
tmp *= x;
tmp %= m;
if (*(s + ) == '^') {
scan(s + , p);
if (p == ) tmp = temp;
//cout << x << ' ' << p << ' ' << m << ' ' << powmod(x, p - 1, m) << endl;
tmp *= powmod(x, p - , m);
tmp %= m;
s += ;
while (isdigit(*s)) s++;
} else s++;
//cout << ret << ' ' << tmp << endl;
ret += tmp;
ret %= m;
tmp = ;
} else {
puts("WTF?...");
cout << s << endl;
while () ;
}
}
return ret;
} bool check(char *s, LL a, LL b, LL m) {
for (LL i = a; i <= b; i++) {
if (cal(s, i, m)) return false;
//cout << s << ' ' << i << ' ' << m << ' ' << cal(s, (LL) i, m) << endl;
}
return true;
} int main() {
int cas = ;
//freopen("in", "r", stdin);
while (cin >> str && strcmp(str, ".")) {
LL D;
char *p = str;
while (*p && *p != '/') p++;
if (*p) {
*(p++) = ;
sscanf(p, "%lld", &D);
} else {
puts("are u kidding?= =");
while () ;
}
if (D > 0x7fffffff) {
puts("fuck you");
while () ;
}
p = fuckbrace(str);
//cout << p << ' ' << D << endl;
LL top = gettop(p);
//cout << top << endl;
if (check(p, , top << , D)) printf("Case %d: Always an integer\n", cas++);
else printf("Case %d: Not always an integer\n", cas++);
}
return ;
}
——written by Lyon