yukicoder : No.1255 ハイレーツ・オブ・ボリビアン

立式部分を世間の情報に頼ってしまったが、改めて考えたらそれほど難しくなかった。
https://yukicoder.me/problems/no/1255

問題

正整数Nが与えられる。
1～2Nが順に並んだ数列を、パーフェクトシャッフルの要領で並べ替えることを繰り返す。
初期状態に戻るのは最低何回シャッフルしたタイミングか。

解法

末尾の要素を除けば、0-indexでp番目にあるカードは2p%(2N-1)番目に移動する。
よって、2^k≡1 (mod 2N-1)となる最小の正整数kを求めよう。
kはφ(2N-1)の約数になるはずなので、φ(2N-1)の約数を総当たりすればよい。

int T;
ll N;

ll modpow(ll a, ll n,ll mo) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
int totient(int v) {
	int ret=v;
	for(int i=2;i*i<=v;i++) if(v%i==0) {
		ret=ret/i*(i-1);
		while(v%i==0) v/=i;
	}
	if(v>1) ret=ret/v*(v-1);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		if(N==1) {
			cout<<1<<endl;
			continue;
		}
		N=2*N-1;
		int v=totient(N);
		ll mi=3LL<<30;
		for(x=1;x*x<=v;x++) if(v%x==0) {
			if(x<mi && modpow(2,x,N)==1) mi=x;
			if(v/x<mi && modpow(2,v/x,N)==1) mi=v/x;
		}
		cout<<mi<<endl;
		
	}
}

まとめ

今回タイトルと問題の対応がよくわからないものが多いけど、なんか元ネタがあるのかな。

|