Submission #2941562

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
typedef long long ll;
ll X,P,A,B,sp,xx;

map<ll,ll> mp;
const ll K=1<<26;

ll mpw(ll n,ll m){
	ll ret=1;
	while(m>0){
		ret*=n;
		ret%=P;
		n*=n;
		n%=P;
		m/=2;
	}
	return ret;
}

ll inv(ll n){
	return mpw(n,P-2);
}

ll bsgs(ll y){
	ll z=y;
	REP(i,sp){
		auto ite=mp.lower_bound(z);
		if (ite->first==z && i*sp+ite->second<P-1){
			return i*sp+ite->second;
		}
		z*=xx;
		z%=P;
	}
	return -1;
}

int main(){
	cin>>X>>P>>A>>B;
	for(sp=1;sp*sp<P;sp++);
	xx=mpw(inv(X),sp);
	ll a=1;
	REP(i,sp){
		mp[a]=i;
		a*=X;
		a%=P;
	}
	ll ans=P;
	if (B-A<=K){
		ll b=mpw(X,A);
		REP(i,B-A+1){
			ans=min(ans,b);
			b*=X;
			b%=P;
		}
	}else{
		ll b=mpw(X,A);
		REP(i,K){
			ans=min(ans,b);
			b*=X;
			b%=P;
		}
		FOR(i,1,ans){
			ll c=bsgs(i);
			if (c<A){
				c=c+(A-c+P-2)/(P-1)*(P-1);
			}
			if (c<=B){
				ans=i;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result