ちょっと手間取った。
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とか)に対応してなかった…。