uvalive 4119 Always an Interger
2024-09-15 00:31:27
差分数列+字符串处理
题意:是让你判断一个整系数多项式的值是否一直都能被一个所给的正整数所整除。
通过对差分数列的不断求导,我们可以发现,对于任意多项式P,我们只需要判断n从1到k+1是否满足就行了,其中,k为多项式P中的最高次数。
可以先了解一下差分数列。
#include <iostream>
#include <cstdio>
#include<cstdlib>
#include<cctype>
#include<string>
#include<vector>
#include<cassert>
using namespace std;
struct Polynomial
{
vector<int >a,p;
void parse_polynomial(string str)
{
int len=str.size(),i=;
while(i<len)
{
int sign=;
if(str[i]=='+')
i++;
if(str[i]=='-')
{
i++;
sign=-;
}
int v=;
while(i<len&&isdigit(str[i]))
v=v*+str[i++]-'';
if(i==len)
{
a.push_back(v);
p.push_back();
}
else
{
assert(str[i] == 'n');
if(v==)
v=;
v*=sign;
if(str[++i]=='^')
{
a.push_back(v);
v=;
i++;
while(i<len&&isdigit(str[i]))
v=v*+str[i++]-'';
p.push_back(v);
}
else
{
a.push_back(v);
p.push_back();
}
}
}
}
int mod(int x,int MOD)
{
int n=a.size();
int ans=;
for(int i=; i<n; i++)
{
int m=a[i];
for(int j=; j<p[i]; j++)
{
m=(long long)m*x%MOD;
}
ans=((long long)ans + m) % MOD;
}
return ans;
}
}; bool check(string str)
{
int p=str.find('/');
Polynomial poly;
poly.parse_polynomial(str.substr(, p-));
int D = atoi(str.substr(p+).c_str());
for(int i=; i<=poly.p[]+;i++)
{
if(poly.mod(i,D))
return false;
}
return true;
} int main()
{
int cas=;
string str;
while(cin>>str)
{
if(str[]=='.')
break;
printf("Case %d: ", cas++);
if(check(str))
printf("Always an integer\n");
else
printf("Not always an integer\n");
}
return ;
}
最新文章
- Linux IPC POSIX 信号量
- BigDecimal 转换类型
- 在windows下新建maven项目
- 深入理解Activity-任务,回退栈,启动模式
- Repeater控件的分页效果
- (二 )VMware workstation 部署虚拟集群实践——并行批量操作环境部署
- Effective Java之并发
- poj 2229 Ultra-QuickSort(树状数组求逆序数)
- 监控代码运行时长 -- StopWatch用法例程
- 转 [ javascript面向对象技术
- Junit4的最简单例子
- 基于hi-nginx的web开发(python篇)——路由装饰器
- 类的命名空间&;组合
- springboot秒杀课程学习整理1-3
- 几种content-type提交以及$_POST 和php://input
- Codeforces 1089E - Easy Chess - [DFS+特判][2018-2019 ICPC, NEERC, Northern Eurasia Finals Problem E]
- Bootstrap 引入文件顺序及IE兼容性js
- Oracle之外键(Foreign Key)使用方法具体解释(二)- 级联删除(DELETE CASCADE)
- [CC-FNCS]Chef and Churu
- .NET基于Eleasticsearch搭建日志系统实战演练