题解 P3306 【[SDOI2013]随机数生成器】

题目链接

Solution [SDOI2013]随机数生成器

(BSGS)

---

题目大意:定义(X_i = aX_{i-1}+b),给定(X_1),求最小的(n)使得(X_n equiv t(mod ; p))

分析:大力化简柿子

[X_1=X_1 ]

[X_2 = aX_1+b ]

[X_3=a^2X_1+ab + b ]

[X_4 = a^3X_1+a^2b+ab+b ]

观察得出(X_n=a^{n-1}X_1+bsum_{i=0}^{n-2}a^i)

发现后面是一个等比数列求和

设(S=sum_{i=0}^{n-2}a^i)

( herefore aS=sum_{i=1}^{n-1}a^i)

( herefore (a-1)S=a^{n-1}-1)

( herefore S= sum_{i=0}^{n-2}=a^{n-1}-1)

继续化简:

(X_n=a^{n-1}X_1+b cdot frac{a^{n-1}-1}{a-1})

(X_n=a^{n-1}X_1+a^{n-1} cdot frac{b}{a-1} - frac{b}{a-1})

(X_n=a^{n-1}(X_1+frac{b}{a-1})-frac{b}{a-1})

有(X_n=a^{n-1}(X_1+frac{b}{a-1})-frac{b}{a-1} equiv t(mod ; p))

( herefore a^{n-1}(X_1+frac{b}{a-1}) equiv t + frac{b}{a-1})

( herefore a^{n-1} equiv frac{t+frac{b}{a-1}}{X_1+frac{b}{a-1}})

直接(BSGS)求解即可,模意义下用费马小定理求一下逆元

然后有一些毒瘤的细节

• (Detail;1)当(X_1=t)时(ans=1)
• (Detail;2)当(a=0)时,(X_1=X_1,X_n equiv b(n eq 2))
• (Detail;3)当(a=1)时,(X_n=X_1+b(n-1)),有(X_1+b(n-1) equiv t(mod;p)),(n=frac{t-X_1}{b}+1),这里用裴蜀定理判断一下有没有解

#include <cstdio>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll p,a,b,X0,t,T;
namespace BSGS{
	unordered_map<ll,int> mp;
	inline ll qpow(ll a,ll b,ll mod){
		ll res = 1,base = a;
		while(b){
			if(b & 1)res = res * base % mod;
			base = base * base % mod;
			b >>= 1;
		}
		return res;
	}
	inline ll gcd(ll a,ll b){
		return !b ? a : gcd(b,a % b);
	}
	inline ll inv(ll x,ll p){
		return qpow(x,p - 2,p);
	}
	inline ll bsgs(ll y,ll z,ll p){
		ll m = sqrt(p) + 1;mp.clear();
		y %= p,z %= p;
		if(y % p == 0 && z)return -1;
		for(ll t = z,i = 0;i < m;i++,t = t * y % p)mp[t] = i;
		for(ll w = qpow(y,m,p),t = w,i = 1;i <= m + 1;i++,t = t * w % p)
			if(mp.find(t) != mp.end())return i * m - mp[t];
		return -1;
	}
}using namespace BSGS;
inline void solve(){
	scanf("%lld %lld %lld %lld %lld",&p,&a,&b,&X0,&t);
	if(X0 == t){
		printf("%d
",1);
		return;
	}
	if(a == 0){
		if(b == t)printf("2
");
		else printf("-1
");
		return;
	}
	if(a == 1){
		ll d = gcd(b,p);
		if((t - X0) % d)printf("-1
");
		else printf("%lld
",1ll * (((t - X0) % p) + p) % p * inv(b % p,p) % p + 1);
		return;
	}
	ll z = t + b * inv(a - 1,p);z %= p;
	z *= inv((X0 + (b * inv(a - 1,p)) % p) % p,p);z %= p;
	ll ans = bsgs(a,z,p);
	if(ans == -1)printf("-1
");
	else printf("%lld
",ans + 1);
}
int main(){
	scanf("%lld",&T);
	while(T--)solve();
	return 0;
}