博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 1069 - Always an integer(数论)
阅读量:5878 次
发布时间:2019-06-19

本文共 1507 字,大约阅读时间需要 5 分钟。

题意:给定一个多项式,推断是否总是整数
思路: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;}

转载地址:http://sfdix.baihongyu.com/

你可能感兴趣的文章
解决Charles https抓包显示<unknown>
查看>>
20155328 《Java程序设计》实验三 敏捷开发与XP实践 实验报告
查看>>
20155328 《网络对抗》 实验八:Web基础
查看>>
Postman带Token的接口测试
查看>>
pip -i 和 -U 参数
查看>>
简单控件的应用(二)—学生管理系统
查看>>
EHCache学习笔记1
查看>>
MySQL 中 savepoint 的使用
查看>>
现实世界的 Windows Azure: IT 公司提高其旗舰产品,为更多客户提供云解决方案
查看>>
main方法中注入Spring bean
查看>>
解决service层无法注入
查看>>
了解lpk.dll是什么病毒以及lpk.dll病毒专杀方法
查看>>
接口隔离原则(设计模式4)
查看>>
StarUML使用说明-指导手册
查看>>
LeetCode--020--括号匹配(java版)
查看>>
LeetCode--083--删除排序链表中的重复元素
查看>>
LeetCode--206--反转链表
查看>>
ios推送通知相关开源项目
查看>>
软件工程第三次作业(2019)
查看>>
hibernate的组成部分
查看>>