Codeforces #183 Div1 D. Rotatable Number

知っていればコードは簡単だけども。
http://codeforces.com/contest/303/problem/D

問題

142857を1～6倍したものは、142857を回転させた形となる。
同様に２進数0011bを1～4倍すると0011bを回転させた形となる。
このような数を巡回数と呼ぶことにする。(leading zeroは含んでも良い)

ここでN,Xが与えられる。
N桁の回転数を構成できるB進数が存在するなら、X未満で最大のBを答えよ。

解法

Editorialがまだ書かれていないが、コメントでリンクされたWikipediaのエントリが答えになる。
Cyclic number - Wikipedia, the free encyclopedia

b進数がL桁の巡回数を作る条件は、

• p = L-1とすると、pはbの約数ではない素数である。(leading zeroを許すならpとbの大小はどちらでも良い)
• さらに、bはpのprimitive root moduloである。

よって、まずpが素数でないなら、解はない。
pが素数なら、B=X-1から順にBをデクリメントしつつprimitive root moduloかどうか判定する。

Bがpのprimitive root moduloかどうか判定するには、B^1～B^(p-2)の範囲に1が現れないことをチェックすればよい。
この処理を愚直にB^(p-2)まで求めても良いが、その場合1.7sかかってかなり時間が危ない。

他の手段としては、(p-1)の約数qを列挙し、B^q==1となるqがないか判定しても良い。
B^(p-2)まで計算するとO(p)かかるが、こちらはO(√p*log(p))で速くなり、0.1sを切れる。

int N,X,P;

bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return true;
}

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

bool is_prim_root_modulo(ll b,ll p) {
	ll cur=1,i;
	if(!isprime(p)) return false;
	for(i=2;i*i<=p-1;i++) if((p-1)%i==0) {
		if(modpow(b,i,p)==1) return false;
		if(modpow(b,(p-1)/i,p)==1) return false;
	}
	return true;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	P=N+1;
	if(isprime(P)){ for(ll B=X-1; B>=2;B--) if(B%P && is_prim_root_modulo(B,P)) return _P("%lld\n",B);}
	_P("-1\n");
}

まとめ

昔から1/7の小数表記は不思議だなーと思っていたけど、今回巡回数の特性を知ってだいぶすっきりした。