1047 Round and Round We Go

問題概要

n桁の数がcyclicであるとは、その数に1〜nを掛けたときに、それぞれが全て元の数を何桁かシフトして得られる数になっていることをいう。

与えられた数がcyclicであるかを判定せよ。
n≦60を満たす。また、leading zeroは元の数の一部としてみなされる。

解法

nが大きいので多倍長整数演算が必要。
最初に元の数をシフトして、得られる数n通りをsetに入れておく。


leading zeroに注意する。

ソースコード

int main(){
	string in,srt;
	while(cin>>in){
		int n=in.size();
		set<string> S;
		rep(i,n){
			S.insert(in);
			rotate(in.begin(),in.begin()+1,in.end());
		}
		
		for(int i=2;i<=n;i++){
			BigNum x=convert(in);
			x=x*convert(i);
			
			stringstream ss; ss<<x;
			string tmp=ss.str();
			if(tmp.size()<n)tmp=string(n-tmp.size(),'0')+tmp;
			if(!S.count(tmp)){
				cout<<in<<" is not cyclic"<<endl; goto END;
			}
		}
		cout<<in<<" is cyclic"<<endl; END:;
	}
	return 0;
}