butsurizuki Beginner Contest 002 : Fracture

ちょっと手間取った。
https://www.hackerrank.com/contests/bbc002/challenges/bbc002-f/problem

問題

N要素の整数列A、素数P、P未満の正整数Xが与えられる。

今変数Vの時刻0における初期値を1とする。
時刻iにおいて、VはV*A[(i-1)%N] % Pに更新される。
VがXと一致する最小の時刻を求めよ。

解法

試しに時刻Nまでシミュレートしてみて、その間にVがXに一致するならそれが解。
また、1周してV=1に戻るなら、以後その手順を繰り返すだけなので解なし。
仮に1周するとk倍されるとする。

仮に時刻aN+bにVがXに一致するとする。
その場合、Vの値は(k^a)*prod(A[0...(b-1)])である。
よってbを決めれば、これは(k^a)=X/prod(A[0...(b-1)])となる最小のaを求める問題となり、これは離散対数問題なのでBaby-Step Giant-Stepで解ける。
幸いNは小さいのでbを総当たりしよう。

int N;
ll mo,X;
ll A[15];

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

ll modlog(ll g,ll a) {  // return g^x=a mod a
	map<ll,ll> M;
	ll cur=1;
	ll sq=sqrt(mo);
	ll i;
	FOR(i,sq) {
		M[cur]=i;
		cur=cur*g%mo;
	}
	
	ll step=cur;
	cur=1;
	ll num=0;
	int lp=0;
	while(1) {
		lp++;
		if(lp>sq+5) return 1LL<<50;
		ll x=a*modpow(cur)%mo;
		if(M.count(x)) return num+M[x];
		cur=cur*step%mo;
		num+=sq;
	}
}
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>mo;
	FOR(i,N) cin>>A[i];
	cin>>X;

	ll mp=1;
	FOR(i,N) {
		if(mp==X) return _P("%d\n",i);
		mp=mp*A[i]%mo;
		if(mp==X) return _P("%d\n",i+1);
	}
	
	if(mp==1) return _P("Fracture\n");
	
	ll mi=1LL<<50;
	ll mp2=1;
	FOR(i,N) {
		ll a=X*modpow(mp2)%mo;
		
		ll v=modlog(mp,a);
		mi=min(mi,v*N+i);
		
		mp2=mp2*A[i]%mo;
	}
	if(mi>1LL<<45) _P("Fracture\n");
	else cout<<mi<<endl;
}

まとめ

BSGSで解がケース(2^x=3 mod 7とか)に対応してなかった…。