bzoj2242 [SDOI2011]计算器——BSGS

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2242

第一次写BSGS，参考了好多好多博客；

然而看到的讲解和模板是一种写法，这道题的网上题解又全都是另一种写法，还是写讲解版吧，注释里是另一种写法；

第一次写嘛，WA到不行，反反复复交了20多遍，原来是 exgcd 写错了囧，改了那么多，不知从何时开始对的...

BSGS意外地挺好写的！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<cmath>

using namespace std;

typedef long long ll;

map<ll,int>mp;

ll T,x,y,Y,Z,P,tp;

ll pw(ll a,ll b,ll mod)

{

    ll ret=;

    for(;b;b>>=1ll,a=(a*a)%mod)

        if(b&)ret=(ret*a)%mod;

    return ret;

}

ll gcd(ll a,ll b){return a%b?gcd(b,a%b):b;}

ll BSGS()

{

    mp.clear();

    if(Y%P==)return -;

    ll m=ceil(sqrt(P));

    ll tmp=Z;//tmp=1

    for(int j=;j<=m;j++)//

    {

        if(!j){mp[tmp]=j; continue;}

        tmp=(tmp*Y)%P;

        mp[tmp]=j;

    }

//    tmp=pw((pw(Y,m,P)),P-2,P); ll nw=Z%P;

    tmp=pw(Y,m,P); ll nw=tmp;//

    for(int i=;i<=m;i++)//

    {

        if(mp[nw])return (i*m%P-mp[nw]%P+P)%P;//i*m+mp[nw]

        nw=(nw*tmp)%P;

    }

    return -;

}

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

    if(!b){x=,y=;return;}

    exgcd(b,a%b,x,y);

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

}

int main()

{

    scanf("%lld%lld",&T,&tp);

    while(T--)

    {

        scanf("%lld%lld%lld",&Y,&Z,&P);

        if(tp==){printf("%lld\n",pw(Y,Z,P));}

        if(tp==)

        {

            ll g=gcd(Y,P);

            if(Z%g){printf("Orz, I cannot find x!\n");continue;}

            Y/=g; P/=g; Z/=g;

            exgcd(Y,P,x,y);

            printf("%lld\n",(x*Z%P+P)%P);//*Z 而非 *g !!!

        }

        if(tp==)

        {

            ll ans=BSGS();

            if(ans==-)printf("Orz, I cannot find x!\n");

            else printf("%lld\n",ans);

        }

    }

    return ;

}