\(\%\%\% Fading\) 早就会了，我最近才理解，当时颓废太多忘学了

1、[SDOI2013]随机数生成器

当天正好在学数列，回来发现用必修五的知识就没了……

不过特判好烦啊。

\(Code\ Below:\)

#include 
    
     #define int long longusing namespace std;int p,a,b,x,t;int gcd(int a,int b){    return (b==0)?a:gcd(b,a%b);}int fast_pow(int a,int b,int p){    int ret=1;    for(;b;b>>=1,a=1ll*a*a%p)        if(b&1) ret=1ll*ret*a%p;    return ret;}int bsgs(int a,int b,int p){    map
     
       mp;    mp.clear();    int t=sqrt(p)+1,val=b,i,j;    for(i=0;i
      
       =0&&i*t-j>=0) return i*t-j;        val=val*a%p;    }    return -1;}signed main(){    int T;    scanf("%lld",&T);    while(T--){        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x,&t);        if(x==t) puts("1");        else if(a==1){            t=(t-x+p)%p;            if(t%gcd(b,p)) puts("-1");            else {                int inv=fast_pow(b,p-2,p);                printf("%lld\n",(t*inv+1==p)?p:(t*inv+1)%p);                            }        }        else if(a==0){            if(b==t) puts("2");            else puts("-1");        }        else {            int val=b*fast_pow(a-1,p-2,p)%p;            int ans=bsgs(a,(t+val)*fast_pow(x+val,p-2,p)%p,p);            if(ans==-1) puts("-1");            else printf("%lld\n",ans+1);        }    }    return 0;}
      
     
    

2、[CQOI2018]破解D-H协议

裸题。

\(Code\ Below:\)

#include 
    
     #define int long longusing namespace std;int a,b,g,p;int fast_pow(int a,int b){    int ret=1;    for(;b;b>>=1,a=a*a%p)        if(b&1) ret=ret*a%p;    return ret;}int bsgs(int a,int b){    map
     
       mp;    mp.clear();    int i,j,val=b,t=sqrt(p)+1;    for(i=0;i
      
       =0&&i*t-j>=0) return i*t-j;        val=val*a%p;    }    return -1;}signed main(){    int T;    scanf("%lld%lld%lld",&g,&p,&T);    while(T--){        scanf("%lld%lld",&a,&b);        printf("%lld\n",fast_pow(b,bsgs(g,a)));    }    return 0;}