正题

题目链接:https://www.luogu.com.cn/problem/P3306

题目大意

给出一个\(p,a,b,x_1,t\)，有\(x_i=ax_{i-1}+b\)

求一个最小的\(n\)使得\(x_n=t\)

解题思路

下标缩一下先变成\(x_0\)会更好算一点，只考虑\(x_0\)的贡献就是\(x_0\times a^n\)，这个比较好搞。

\(b\)的贡献的话，对于第\(i\)次加入的\(b\)贡献是\(a^{n-i}\)总共也就是\(b\times \sum_{i=0}^{n-1}a^i\)

通项公式一下合起来就是

\[x_0a^n+\frac{a^n-1}{a-1}b=t
\]

把\(a^n\)提到前面来就是

\[a^n=\frac{t(a-1)+b}{xa-x+b}
\]

后面那个是已知的，然后就是上\(\text{BSGS}\)就好了。

需要注意的是如果\(a=1\)就不能用通项公式了，得上\(\text{exgcd}\)来搞。

要特判的东西有点多就不多讲了

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<cmath>

#define ll long long

using namespace std;

ll T,p,a,b,x,t,ans;

map<ll,ll> v;

ll power(ll x,ll b){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%p;

        x=x*x%p;b>>=1;

    }

    return ans;

}

ll exgcd(ll a,ll b,ll &x,ll &y){

	if(!b){

		x=1;y=0;

		return a;

	}

	ll d=exgcd(b,a%b,x,y);

	ll z=x;x=y;y=z-a/b*y;

	return d;

}

void works(ll a,ll b,ll p){

	ll x,y;

	ll d=exgcd(a,p,x,y);

	if(b%d){

		printf("-1\n");

		return;

	}

	x*=b/d;y*=b/d;

	printf("%lld\n",(x%(d*p)+d*p)%(d*p)+1);

}

ll work(ll a,ll b,ll p){

    if(!a&&!b)return 1;

    if(!a)return -2;

    ll t=sqrt(p)+1;v.clear();

    for(ll i=0,z=1;i<t;i++,z=z*a%p)

        v[z*b%p]=i;

    a=power(a,t);

    if(b==1||!a)return 1;

    else if(!a)return -2;

    ll ans=1e18;

    for(ll i=0,tmp=1;i<=t;i++,tmp=tmp*a%p){

        ll j=(v.find(tmp)!=v.end())?v[tmp]:-1;

        if(j>=0&&i*t-j>=0)ans=min(ans,i*t-j);

    }

    if(ans==1e18)return -2;

    return ans;

}

signed main()

{

    scanf("%lld",&T);

    while(T--){

        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x,&t);

        if(!a&&!t&&b){puts("-1");continue;}

        if(x==t){puts("1");continue;}

        if(a==1){

            works(b,(t-x+p)%p,p);

            continue;

        }

        t=(t*(a-1)+b)%p;x=(x*a-x+b+p)%p;

        t=t*power(x,p-2)%p;t=(t+p)%p;

        printf("%lld\n",work(a,t,p)+1);

    }

    return 0;

}

巴特西

P3306-[SDOI2013]随机数生成器【BSGS】

正题

题目大意

解题思路

code

最新文章

热门文章