首页 > 代码库 > uva 1069 - Always an integer(数学+暴力)
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 <cstdio>
#include <cstring>
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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。