LA 4119 - Always an integer

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2120

假设式子的最高幂次为k 则只需要测试1到k+1就可以了

原理见 刘汝佳的《算法竞赛入门经典入门指南》 P123

字符串需要自己处理,比较繁琐 一定要细心

代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue> #define ll long long
#define lint long long
using namespace std; const int N=100005;
ll a[N];
ll powerMod(ll x,ll y,ll M)
{//cout<<x<<" "<<y<<" "<<M<<endl;
ll tmp=1;
while(y)
{
if(y&1)
tmp=tmp*x%M;
x=x*x%M;
y=y>>1;
}
//cout<<(tmp%M)<<endl;
return tmp%M;
}
void func(string s)
{//cout<<s<<endl;
if(s.size()==0) return; int m=s.find('n');
if(m==-1)
m=s.size();
int type=(s[0]=='-')?-1:1;
ll tmp=0;
//int l=;cout<<l<<" "<<m<<endl;
for(int i=(s[0]=='+'||s[0]=='-')?1:0;i<m;++i)
{//cout<<i<<" "<<tmp<<endl;
tmp=tmp*10+s[i]-'0';
}
if(tmp==0) tmp=1;
tmp=tmp*type;
m=s.find('n');//cout<<m<<endl;
if(m==-1) a[0]=tmp;
else
{//cout<<"in1"<<endl;return ;
int k=s.find('^');
if(k==-1)
a[1]=tmp;
else
{//cout<<"in2"<<endl;
int x=0;
for(int i=k+1;i<s.size();++i)
{
x=x*10+s[i]-'0';
}
//cout<<x<<" "<<tmp<<endl;
a[x]=tmp;
}
}
//cout<<"return"<<endl;
}
bool solve(string s)
{
memset(a,0,sizeof(a));
int k=s.find('/');
ll M=0;
for(int i=k+1;i<s.length();++i)
M=M*10+s[i]-'0';
string stmp;
for(int i=(s[0]=='(')?1:0;i<k&&s[i]!=')';++i)
{
if(s[i]=='+'||s[i]=='-')
{
func(stmp);
stmp.clear();
}
stmp.push_back(s[i]);
}
func(stmp);
for(ll i=1;i<=101;++i)
{//cout<<i<<endl;
ll tmp=0;
for(ll j=0;j<=100;++j)
{
//cout<<j<<" "<<a[j]<<endl;
tmp=(tmp+a[j]*powerMod(i,j,M))%M;
}
if(tmp!=0)
return false;
}
return true;
}
int main()
{
//freopen("data.in","r",stdin);
int ca=1;
string s;
while(cin>>s)
{
if(s==".")break;
if(solve(s))
printf("Case %d: Always an integer\n",ca++);
else
printf("Case %d: Not always an integer\n",ca++);
}
return 0;
}
上一篇:python 全栈开发,Day111(客户管理之 编辑权限(二),Django表单集合Formset,ORM之limit_choices_to,构造家族结构)


下一篇:vim编辑器配置修改