LA 4119 - Always an integer
3269 ワード
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2120
式の最高べき乗数がkであると仮定すると,1からk+1をテストするだけでよい.
原理は劉汝佳の《アルゴリズムコンテスト入門経典入門ガイド》P 123を参照
文字列は自分で処理する必要があります.煩雑なので注意しなければなりません.
コード:
式の最高べき乗数がkであると仮定すると,1からk+1をテストするだけでよい.
原理は劉汝佳の《アルゴリズムコンテスト入門経典入門ガイド》P 123を参照
文字列は自分で処理する必要があります.煩雑なので注意しなければなりません.
コード:
#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
",ca++);
else
printf("Case %d: Not always an integer
",ca++);
}
return 0;
}