PKU 3284 Eventually periodic sequence
http://poj.org/problem?id=3284
+*%からなる関数f(x)が与えられるので、
ある入力からはじめて、この関数を繰り返し適用したときの周期を求めろというような問題
計算量がけっこうでかいようような気がしましたが間に合ってよかったです。
構文解析的なことも必要ないので、愚直にやる
int n,N; int i2s(string &a){ int ret=0; FOR(it,a) ret=(ret*10+*it-'0')%N; return ret; } char op[1000]; ll val[1000]; int app[11000000]; ll st[130]; int sts; void solve(){ int cnt = 0; string in; while(cin >> in){ if(in=="N"){ cin >> in; break; } op[cnt] = in[0]; val[cnt] = i2s(in); ++cnt; } int cn=1; rep(i,N) app[i] = 0; while(true){ int idx = 0; sts = 0; while(idx < cnt){ ll a,b; switch(op[idx]){ case '+': a=st[--sts]; b=st[--sts]; st[sts++]=(a+b)%N; break; case '*': a=st[--sts]; b=st[--sts]; st[sts++]=(a*b)%N; break; case 'x': st[sts++]=n; break; default: st[sts++]=val[idx]; } ++idx; } n=st[0]; //cout << n << ' ' << app[n] << endl; if(app[n]){ cout << cn - app[n] << endl; return; } app[n] = cn++; } } main(){ while(cin >> N >> n, N) solve(); }