PKU 2635 The Embarrassed Cryptographer
http://poj.org/problem?id=2635
(4<=k <=10^100)となるkと、(2<=l<=10^6)となるlが与えられる。
この時、l未満の素数でkの因数となるものがあるかどうかを判定するという問題。
javaに頼らないと解けないかと思いましたが、あまりが0であるかどうかを確認すればいいので、4桁ごとに区切ってあまりを計算しました。
未満と以下を読み間違えてたり、オーバーフローやらなんやらで結構WAをもらいました。
bool pr[1000001]; int npr[1000000],pos; main(){ pr[0]=pr[1]=true; for(int i=2;i<1000001;i++){ if(pr[i])continue; for(int j=i*2;j<1000001;j+=i)pr[j]=true; } rep(i,1000001) if(pr[i]==false)npr[pos++]=i; string in; int l; while(cin>>in>>l,l){ vector<int> num; int t=0; reverse(ALL(in)); int sz=SZ(in); rep(i,sz){ int base=1; rep(j,4){ if(i<sz)t+=(in[i++]-'0')*base; base*=10; } --i; num.pb(t); t=0; } reverse(ALL(num)); bool ok=true; rep(i,pos){ if(npr[i]>=l)break; ll mo=0; rep(k,SZ(num)){ mo=(mo*10000+num[k])%npr[i]; } if(mo==0){ ok=false; cout<<"BAD "<<npr[i]<<endl; break; } } if(ok)cout<<"GOOD"<<endl; } }