http://www.lydsy.com/JudgeOnline/problem.php?id=3122

题意

已知Xi+1=(aXi + b)mod p；

给定X1，a，b，p(质数），t

求第一个满足Xn=t的n

题解

把原式化开，得

Xn=[a^(n-1)*X1+b*(a^(n-2)+a^(n-3)+..+a^0)]mod p;

分情况讨论

①X1=t时，ans=1；

②a=0时，

    1.b=t时,ans=2;

    2.b!=t时,ans=-1;

③a=1时，

    Xn=[X1+b*(n-1)]mod p=t

    移向之后，相当于求xb+yp=(t-X1)mod p;

    扩展gcd，ans=x+1;

④a>1时，

    Xn=[a^(n-1)*X1+b*(a^(n-1)-1)/(a-1)]mod p

    设c=(a-1)在模p意义下的逆元，即c=(a-1)^(p-2);

    Xn=[a^(n-1)*X1+bc*(a^(n-1)-1)]mod p

    化简得Xn=[(X1+bc)*a^(n-1)-bc]mod p=t

    令q=X1+bc，t`=(t+bc)mod p,

    移向后相当于求[q*a^(n-1)]mod p=t'

    接下来我的做法是，先求xq+yp=t'的解x；

    问题变为求a^x` mod p=x，ans=x`+1。就和山东11年的计算器那题一样了。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
typedef long long ll;
const int H=1000001;
int f[H],r[H];
ll p,a,b,x1,x,y,t;
 
ll km(ll a,ll k)
{
    if(!a) return 0;
    ll t=a,q=1;
    while(k)
    {
        if(k&1) q=((q%p)*(t%p))%p;
        t=((t%p)*(t%p))%p;
        k=k>>1;
    }
    return q;
}
void gcd(ll a,ll b,ll c)
{
    if(!b)
        if(!(c%a))
        {
            x=c/a;y=0;
            return;
        }
        else
        {
            x=-1;return;
        }
    gcd(b,a%b,c);
    if(x==-1) return;
    ll t=y;y=x-((a/b)*y);x=t;
}
       
void work1()
{
    t=(t-x1+p)%p;
    x=y=0;
    gcd(b,p,t);
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
        x++;
    }
    printf("%lld\n",x);
}
void work2()
{
    ll c=km(a-1,p-2);
    t=(t+((b*c)%p))%p;
    ll q=(x1+((b*c)%p))%p;
    x=y=0;
    gcd(q,p,t);
    if(x==-1)
    {
        puts("-1");return;
    }
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
    }
    int m=int(floor(sqrt(p)+1)),b=km(a,p-1-m);;
    memset(f,255,sizeof(f));
    memset(r,255,sizeof(r));
    ll now=1;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1) h=(h+1)%H;
        f[h]=now;r[h]=i;now=now*a%p;
    }
    now=x%p;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1)
        {
            if(f[h]==now)
            {
                printf("%d\n",i*m+r[h]+1);
                return;
            }
            h=(h+1)%H;
        }
        now=now*b%p;
    }
    puts("-1");
}
 
void work()
{
    if(x1==t){puts("1");return;}
    if(a==0)
    {
        if(b==t) puts("2");
        else puts("-1");
        return;
    } 
    if(a==1)
    {
        work1();
        return;
    }
    work2();
}
     
int main()
{
    int T;scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        work();
    }
}