计算器

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2369 字
给定T组数据与类型K，分别求y^zmodp、
一本通
例
正文

/*
原题：「一本通 6.4 例 6」计算器（SDOI 2011）
题意：给定 T 组数据与类型 K，分别求 y^z mod p、最小非负 x 使 x·y≡z(mod p)、最小非负 x 使 y^x≡z(mod p)。
思路：K=1 用快速幂求 y^z mod p；K=2 用扩展欧几里得解线性同余方程 a·x≡b(mod p)；K=3 在质数模 p 下用大步小步(BSGS)求离散对数。
复杂度：K=1/2 为 O(log p)；K=3 为 O(√p)，空间 O(√p)。
易错点：BSGS 需特判 z≡1(答案 0) 与 y≡0(mod p)；无解时输出 "Orz, I cannot find x!"；所有模运算结果要归一化到 [0,p)。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
// 快速幂：a^b mod p
ll qpow(ll a,ll b,ll p){
    ll r=1%p;
    a%=p;
    while(b){
        if(b&1)r=r*a%p;
        a=a*a%p;
        b>>=1;
    }
    return r;
}
// 扩展欧几里得：a·x + b·y = gcd(a,b)
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
// 解线性同余 a·x ≡ b (mod m)，返回最小非负解；无解返回 -1
ll solveLin(ll a,ll b,ll m){
    a%=m; if(a<0)a+=m;
    b%=m; if(b<0)b+=m;
    ll x0,y0;
    ll g=exgcd(a,m,x0,y0);
    if(b%g!=0)return -1;
    ll mg=m/g;
    x0=((x0%mg)+mg)%mg;
    x0=(__int128)x0*(b/g)%mg;
    return x0;
}
// BSGS：解 y^x ≡ z (mod p)，p 为质数，返回最小非负 x；无解返回 -1
ll bsgs(ll y,ll z,ll p){
    y%=p; z%=p;
    if(z==1)return 0;          // y^0 = 1
    if(y==0){                  // 仅 x=1 时 y^x ≡ 0
        return (z==0)?1:-1;
    }
    ll m=(ll)ceil(sqrt((double)p));
    unordered_map<ll,ll> mp;
    mp[z]=0;                   // z·y^0
    ll cur=z;
    for(ll j=1;j<m;j++){
        cur=cur*y%p;
        auto it=mp.find(cur);
        if(it==mp.end()||j>it->second)mp[cur]=j;  // 存最大 j -> 得到最小 x
    }
    ll t=qpow(y,m,p);          // y^m
    ll now=1;
    ll ans=-1;
    for(ll i=1;i<=m;i++){
        now=now*t%p;
        auto it=mp.find(now);
        if(it!=mp.end()){
            ll x=i*m-it->second;
            if(ans==-1||x<ans)ans=x;
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll T,K;
    if(!(cin>>T>>K))return 0;
    while(T--){
        ll y,z,p;
        cin>>y>>z>>p;
        if(K==1){
            cout<<qpow(y,z,p)<<'\n';
        }else if(K==2){
            // x·y ≡ z (mod p)
            ll x=solveLin(y,z,p);
            if(x==-1)cout<<"Orz, I cannot find x!\n";
            else cout<<x<<'\n';
        }else{
            // y^x ≡ z (mod p)
            ll x=bsgs(y,z,p);
            if(x==-1)cout<<"Orz, I cannot find x!\n";
            else cout<<x<<'\n';
        }
    }
    return 0;
}
计算器

正文

一本通·提高篇的其它内容
