PKU 2939 Flavius Josephus Reloaded
http://poj.org/problem?id=2939
変則的なヨセフスの問題の生き残る人数を答えろというような問題。
mapだとTLEだったのでハッシュでシミュレートして通しました。
long longでもa*x*xは桁あふれの可能性ありなんですが、サンプルが親切で助かりました。
typedef struct _node{ int key,val; _node*next; }node; const int MOD=3000000; int sz; node*hash[MOD]; node ent[3000000]; int get(int key){ int ha=key%MOD; for(node*p=hash[ha];p;p=p->next) if(p->key==key)return p->val; return 0; } void insert(int key,int val){ int ha=key%MOD; node*p=hash[ha]; hash[ha]=ent+sz++; hash[ha]->val=val; hash[ha]->key=key; hash[ha]->next=p; } main(){ int n,a,b; while(scanf("%d",&n),n){ scanf("%d%d",&a,&b); sz=0; memset(hash,0,sizeof(hash)); ll x=0; int t=1; while(1){ if(get(x)){ cout<<n-t+get(x)<<endl; break; } insert(x,t++); x=((x*x)%n*a+b)%n; } } }