AtCoder ARC #042 : D - あまり

以前このアルゴリズム見たときは「すげー」と思ったけど、この正解者数だと割と有名なアルゴリズムなのかな。
…と思ったら埋め込みや愚直ループで通してる人も結構いたようだ。
http://arc042.contest.atcoder.jp/tasks/arc042_d

問題

以下の条件を満たす整数X,P,A,Bが与えられる。

• これらは乱数生成機で生成されている。
• Pは素数である。
• 1≦X＜P＜2^31、0≦A≦B＜2^31

X^i mod P (A≦i≦B)の最小値を求めよ。

解法

以下の２つの考え方を組み合わせる。
yukicoder : No.97 最大の値を求めるくえり - kmjp's blog
UTPC 2014: L - セミ時雨ハッシュ - kmjp's blog

まず簡単なケースを処理してしまおう。
フェルマーの小定理より、A～Bの間に(P-1)の倍数があれば、解は1である。
以下、A～Bの間に(P-1)の倍数がない場合を考える（A,Bは(P-1)の剰余を取った値にしておく)

B-Aが比較的小さい(10^8位？)までなら、愚直にX^A～X^Bを総当たりしてしまおう。
B-Aが大きい場合、10^8以上なら、X^A～X^Bは1～(P-1)の間で(B-A+1)個の値を取ることになるので、Pが2^31近い場合でも1/20位の割合で含まれることになる。

よって、X^i=1,2,3.... となるiを順に求めていけば、20位まで探索する間にA≦i≦Bとなるiが現れることが期待できる。

あとはX^i=Qとなるiの求め方だが、これはいわゆる離散対数問題であり、上記UTPCの問題のようにBaby-Step Giant-Stepアルゴリズムで解くことができる。
自分が(UTPCを解いた当時)参考にしたのは以下のPDF。
https://math.berkeley.edu/~sagrawal/su14_math55/notes_shank.pdf

ll X,A,B,P,XA;
ll mo;
map<ll,int> MM;

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>P>>A>>B;
	if(A/(P-1) != B/(P-1)) return _P("1\n");
	A %= (P-1);
	B %= (P-1);
	
	mo=P;
	
	XA=modpow(X,A);
	B-=A;
	
	if(B<=100000000) {
		ll mi=XA;
		FOR(i,B) {
			XA=XA*X%mo;
			mi=min(mi,XA);
		}
		cout<<mi<<endl;
	}
	else {
		
		ll cur=1, sq;
		for(sq=0;sq*sq<=P;sq++) {
			MM[cur]=sq;
			cur=cur*X%P;
		}
		
		ll re=modpow(X),xsq=1;
		FOR(i,sq) xsq=xsq*re%P;
		
		ll XAr=modpow(XA);
		for(ll a=1;a<=P;a++) {
			ll tar=a*XAr%mo;
			ll st=1;
			FOR(i,sq) {
				if(MM.count(tar) && sq*i+MM[tar]<=B) return _P("%lld\n",a);
				tar=tar*xsq%mo;
			}
		}
	}
}

まとめ

UTPCちゃんと解いておいてよかった。