BZOJ 2242 SDOI2011 计算器

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

第一问快速幂

第二问是扩展欧几里得算法求不定方程

第三问使用BSGS算法求离散模对数

三个函数直接看代码吧……纯板子题……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get_num(){
    ll num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
ll y,z,p;
map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b > 0){
        if(b & 1){
            ret = ret * a;
            ret %= mod;
        }
        b >>= 1;
        a = a * a;
        a %= mod;
    }
    return ret;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(b == 0){
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,d,x,y);
    ll tp = x;
    x = y;
    y = tp - (a / b) * y;
    return;
}
void BSGS(ll y,ll z,ll p){
    mp.clear();
    y %= p;
    if(y == 0 && z == 0){
        cout << "1" << endl;
        return;
    }
    else if(y == 0){
        cout << "Orz, I cannot find x!" << endl;
        return;
    }
    ll s = ceil(sqrt(p)),t = 1;
    mp[1] = s + 1;
    for(int i = 1;i < s;++i){
        t = t * y;
        t = t % p;
        if(!mp[t])mp[t] = i;
    }
    ll v = quick_pow(y,p-s-1,p);
    ll ret = 1;
    for(ll k = 0;k < s;++k){
        int i = mp[ret * z % p];
        if(i){
            if(i == s + 1)i = 0;
            cout << k*s + i << endl;
            return;
        }
        ret = ret * v;
        ret %= p;
    }
    cout << "Orz, I cannot find x!" << endl;
}
int T,K;
ll ans1,ans2;
int main(){
    cin >> T >> K;
    while(T--){
        if(K == 1){
            y = get_num();
            z = get_num();
            p = get_num();
            cout << quick_pow(y,z,p) << endl;
        }
        else if(K == 2){
            y = get_num();
            z = get_num();
            p = get_num();
            ll g = __gcd(y,p);
            if(z % g)cout << "Orz, I cannot find x!" << endl;
            else{
                z /= g;
                y /= g;
                p /= g;
                exgcd(y,p,g,ans1,ans2);
                ans1 = ans1 * z;
                if(ans1 >= 0)
                    ans1 = ans1 % p;
                else
                    ans1 = (ans1 % p) + p;
                ans1 %= p;
                cout << ans1 << endl;
            }
        }
        else if(K == 3){
            y = get_num();
            z = get_num();
            p = get_num();
            BSGS(y,z,p);
        }
    }
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00