luoguP3306 [SDOI2013]随机数生成器

题意

将\(x_1,x_2,x_3...x_n\)写出来可以发现通项为\(a^{i-1}*x_1+b*\sum\limits_{j=0}^{i-2}a^j=a^{i-1}*x_1+b*\frac{1-a^{i-1}}{1-a}=(x_1-\frac{b}{1-a})a^{i-1}+\frac{b}{1-a}\)

所求变为求一个\(i\)满足：

\(t\equiv (x_1-\frac{b}{1-a})a^{i-1}+\frac{b}{1-a}\pmod{p}\)

\(a^{i-1}\equiv \frac{t-(\frac{b}{1-a})}{x_1-\frac{b}{1-a}}\pmod{p}\)

上BSGS即可，注意特判\(a=0/1\)。

\(a=0\)：对于任意\(i,x_i=b\)

\(a=1\)：\(x_i=x_1+(i-1)*b\)

解下对应的方程即可。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int T;

ll a,b,x1,mod,goal;

inline ll power(ll x,ll k,ll mod)

{

	ll res=1;

	while(k)

	{

		if(k&1)res=res*x%mod;

		x=x*x%mod;k>>=1;

	}

	return res;

}

inline ll inv(ll x,ll mod){return power(x,mod-2,mod);}

inline ll BSGS(ll a,ll b,ll mod)

{

	if(b==1)return 0;

	unordered_map<ll,int>mp;mp.clear();

	a%=mod,b%=mod;

	ll t=ceil(sqrt(mod));

	ll now=1;

	for(int i=0;i<=t;i++)mp[b*now%mod]=i,now=now*a%mod;

	a=power(a,t,mod);

	if(!a)return !b?1:-1;

	now=a;

	for(int i=1;i<=t;i++)

	{

		if(mp.count(now))return i*t-mp[now];

		now=now*a%mod;

	}

	return -1;

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%lld%lld%lld%lld%lld",&mod,&a,&b,&x1,&goal);

		if(x1==goal){puts("1");continue;}

		if(!a){puts(b==goal?"2":"-1");continue;}

		if(a==1)

		{

			goal=((goal-x1)%mod+mod)%mod;

			ll d=__gcd(b,mod);

			if(goal%d){puts("-1");continue;}

			ll res=(goal*inv(b,mod)+1)%mod;

			if(!res)res=mod;

			printf("%lld\n",res);

			continue;

		}

		ll res=BSGS(a,((goal-b*inv(1-a,mod)%mod)%mod+mod)%mod*inv(((x1-b*inv(1-a,mod)%mod)%mod+mod)%mod,mod)%mod,mod);

		printf("%lld\n",res==-1?res:res+1);

	}

	return 0;

}

巴特西

luoguP3306 [SDOI2013]随机数生成器

最新文章

热门文章