icontofig | 发布于 2019-11-06 22:11:12 | 阅读量 353 | 数论 数学
发布于 2019-11-06 22:11:12 | 数论 数学

题解

第一问快速幂

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

第三问使用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;
}



内容更新于: 2019-11-06 23:02:10
链接地址: http://blog.leanote.com/post/icontofig/920a62106e76

上一篇: 可持久化并查集 洛谷P3401

下一篇: CCPC2017哈尔滨站 Server——01分数规划+树状数组

353 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航