[SDOI2011]计算器（exgcd&BSGS）

k=1：裸的快速幂
k=2：xy=z+kp，直接exgcd，这个可以不用解释了，不懂的同学可以看代码

k=3：裸的BSGS

重点是k=3（BSGS学习）
a^x=b(mod p)求解这个同余方程
只能求gcd(a,p)=1的情况。
如何求解？很容易发现解一定位于{0,p-1}之间，设q=ceil(√p)，然后x可以表示成cq-d
因为a^x=b(mod p)，所以a^cq=b*a^d(mod p)
于是可以这样考虑：枚举d∈[1,q]，将值插入哈希表，如有重复的则只记录最大的d，因为本题是求最小解，再枚举c=1...q，查询a^cq是否在哈希表内，如果在就可以直接跳出来。

注意要特判a或b等于0的情况就可以了。

不说太多了，直接上模板：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

map<int,int>hsh;

ll y,z,p;

ll qpow(ll a,ll b)

{

    a%=p;

    ll ret=;

    while(b)

    {

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

        a=a*a%p,b>>=;

    }

    return ret;

}

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

{

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

    ll ret=exgcd(b,a%b,y,x);y-=a/b*x;

    return ret;

}

void solve2(ll a,ll b)

{

    ll x,y,ans,d,s;

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

    if(b%d){puts("Orz, I cannot find x!");return;}

    ans=b/d*x;

    s=p/d;

    ans=(ans%s+s)%s;

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

}

void solve3()

{

    y%=p,z%=p;

    if(!y)

    {

        if(!z)puts("");else puts("Orz, I cannot find x!");

        return;

    }

    ll m=ceil(sqrt(p)),v=qpow(y,p-m-),e=,ret;

    hsh.clear();

    hsh[]=m+;

    for(ll i=;i<=m;i++)

    {

        e=e*y%p;

        if(!hsh[e])hsh[e]=i;

    }

    ret=-;

    for(ll i=;i<m;i++)

    {

        if(hsh[z]){ret=i*m+(hsh[z]==m+?:hsh[z]);break;}

        z=z*v%p;

    }

    if(ret==-)puts("Orz, I cannot find x!");

    else printf("%d\n",ret);

}

int main()

{

    int T,k;

    scanf("%d%d",&T,&k);

    while(T--)

    {

        scanf("%lld%lld%lld",&y,&z,&p);

        if(k==)printf("%lld\n",qpow(y,z));

        else if(k==)solve2(y,z);

        else solve3();

    }

}

秒客网

[SDOI2011]计算器（exgcd&BSGS）

相关文章