计算器

有注释

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y;
void exgcd(ll a,ll b)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b);
    ll cx=x,cy=y;
    x=cy; y=cx-a/b*cy;
}

inline ll qp(ll a,ll b,ll mod)
{
    a%=mod;
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;    
    }
    return res;
}

int main()
{
    int t,k;
    while(cin>>t>>k)
    {
        if(k==1)
        {
            ll a,b,p;
            while(cin>>a>>b>>p)
            {
                cout<<qp(a,b,p)<<endl;
            }
        }
        else if(k==2)
        {
            ll a,b,p;
            while(cin>>a>>b>>p)
            {
                if(b%(__gcd(a,p))!=0)   puts("Orz, I cannot find x!");
                else 
                {
                    exgcd(a,p);
                    cout<<(x*b/__gcd(a,p)%(p/(__gcd(a,p)))+p/(__gcd(a,p)))%p/(__gcd(a,p))<<endl;
                }
            }
        }
        else
        {
            //解一个这种a^x%p=z%p方程.令x=i*m-j.其中m=sqrt(p).0<=j<m.0<=i<=m.原式就成了a^(i*m)%p=b*(a^j)%p.因为求min,先把j求出即可
            unordered_map<ll,ll>hash;
            ll ans,a,b,p;
            while(cin>>a>>b>>p)
            {
                hash.clear();
                ll m=sqrt(p)+1;
                ll flag=0;
                for(ll j=0;j<m;j++) hash[b*qp(a,j,p)%p]=j;
                a=qp(a,m,p);
                if(a==0) 
                {
                    puts("Orz, I cannot find x!"); 
                    continue;
                }//仔细看看同余定理
                for(ll i=0;i<=m;i++)
                {
                    ll res=qp(a,i,p);
                    if(hash.find(res)!=hash.end())
                    {
                        ans=i*m-hash[res];
                        flag=1;
                        break;
                    }
                }
                if(flag)    cout<<ans<<endl;
                else        puts("Orz, I cannot find x!");
            }
        }    
    }
    return 0;
}