博客食用效果更佳

蒟蒻做的第一道$BSGS$的题目

简单写一下吧

对于操作$1和2$没啥好说的，一个快速幂，一个扩展欧几里得

对于操作$3$，就是让你求$a^x \equiv b(\mod p)$

设$x=i*t-j$,其中$t= \sqrt p，0 \le j \le t-1$

则方程变为$a^{i*t-j} \equiv b (\mod p)$

进一步变形得：$(a^{t})^i \equiv b*a^j (\mod p)$

对于$j \in [0,t-1]$，我们把$b*a^j \mod p$插入到一个$hash$表里

然后枚举$i$，$i \in [0,t]$,计算出$(a^t)^i \mod p$然后在$hash$表里查询是否存在对应的$j$

/*
@ author:pyyyyyy
-----思路------

-----debug-------

*/
#include<bits/stdc++.h>
#include<map>
#define int long long  
using namespace std;
int T,K;
int ksm(int a,int b,int p)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=(ret*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ret%p;
}
int bsgs(int a,int b,int p)
{
    map<int,int> hash;
    hash.clear();
    b%=p;
    int t=(int)sqrt(p)+1;
    for(int j=0;j<=t-1;++j) 
    {
        int val=b*ksm(a,j,p)%p;
        hash[val]=j;
    }
    a=ksm(a,t,p);//a^t
    if(a==0) return b==0 ? 1 : -1;
    for(int i=0;i<=t;++i)
    {
        int val=ksm(a,i,p);//(a^t)^i
        int j=hash.find(val)==hash.end() ? -1 : hash[val] ;
        if(j>=0&&i*t-j>=0) return i*t-j;
    }
    return -1;  
}
int exgcd(int a,int b,int &x,int &y)
{
    if(!b) {x=1;y=0;return a;}
    int d=exgcd(b,a%b,x,y);
    int z=x;x=y;y=z-y*(a/b);
    return d;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin>>T>>K;
    while(T--)
    {
        int y,z,p;
        cin>>y>>z>>p;
        if(K==1)
            cout<<ksm(y,z,p)%p<<'\n';
        if(K==2)
        {
            int x0=0,y0=0;
            int d=exgcd(y,p,x0,y0);
            if(z%d!=0) cout<<"Orz, I cannot find x!\n";
            else{
                int x=x0*(z/d);
                x=(x%(p/d)+(p/d))%p;
                cout<<x<<'\n';
            }
        }
        if(K==3)
        {
            int ans=bsgs(y,z,p)%p;
            if(ans==-1) cout<<"Orz, I cannot find x!\n";
            else cout<<ans<<'\n';
        }

    }
    return 0;
}