洛谷2485 [SDOI2011]计算器

题意

给出 $y,z,p$ ， 要求计算下列式子的值：

1. $y^z\bmod p$
2. 满足 $x\times y\equiv z\ (\bmod \ p)$ 的最小非负整数 $x$；
3. 满足 $y^x\equiv z\ (\bmod \ p)$ 的最小非负整数 $x$。

题解

三合一题目。

1. 快速幂
2. $\text{exgcd}$
3. $\text{bsgs}$（保证了 $p$ 是质数所以不用 $\text{exbsgs}$）

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll t,k,a,b,c;

inline ll POW(ll x,ll y,ll ha)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans%ha;
}

ll exgcd(ll l,ll r,ll &x,ll &y)
{
    if (r==0)
    {
        x=1; y=0;
        return l;
    }
    ll ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline ll bsgs() //a^{ky}=b*a^{m}
{
    if (a%c==0 && b) return -1;
    if (b%c==1) return 0;
    map <ll,ll> mp;
    ll y=sqrt(c-1)+1;
    ll right=b%c;
    for (ll i=0;i<y;i++) ///m
    {
        mp[right]=i+1;
        right=right*a%c;
    }
    ll once=POW(a,y,c);
    ll left=once%c;
    for (ll i=1;i<=y;i++) //k
    {
        if (mp[left]) return i*y-mp[left]+1;
        left=left*once%c;
    }
    return -1;
}

signed main()
{
    t=read(); k=read();
    while (t--)
    {
        a=read(); b=read(); c=read();
        if (k==1) printf("%lld\n",POW(a,b,c));
        else if (k==2)
        {
            ll x=0,y=0;
            ll g=exgcd(a,c,x,y);
            if (b%g) puts("Orz, I cannot find x!");
            else printf("%lld\n",(x*b/g%(c/g)+c/g)%(c/g));
        }
        else if (k==3)
        {
            ll ans=bsgs();
            if (ans==-1) puts("Orz, I cannot find x!");
            else printf("%lld\n",ans);
        }
    }
    return 0;
}