-数论-扩展欧几里得-BSGS- [BZOJ 2242][SDOI2011]计算器

题目描述

你被要求设计一个计算器完成以下三项任务：

1、给定y、z、p，计算y^z mod p 的值；

2、给定y、z、p，计算满足xy ≡z(mod p)的最小非负整数x；

3、给定y、z、p，计算满足y^x ≡z(mod p)的最小非负整数x。

为了拿到奖品，全力以赴吧！

输入格式

输入文件calc.in 包含多组数据。

第一行包含两个正整数T、K，分别表示数据组数和询问类型（对于一个测试点内的所有数

据，询问类型相同）。

以下T 行每行包含三个正整数y、z、p，描述一个询问。

输出格式

输出文件calc.out 包括T 行.

对于每个询问，输出一行答案。

对于询问类型2 和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”。

输入样例

3 1
2 1 3
2 2 3
2 3 3

输出样例

2
1
2

说明

【数据规模和约定】

对于100%的数据，1<=y,z,p<=10^9，P为质数，1<=T<=10。

Solution

对于操作1，我们用快速幂

对于操作2，我们用扩展欧几里得

对于操作3，我们用BSGS（北上广深）

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#define ll long long
ll qpow(ll a , ll b , ll m) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (res * a) % m;
        b >>= 1;
        a = (a * a) % m;
    }
    return res % m;
}
ll exgcd(ll a , ll b , ll &x , ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b , a % b , x , y);
    ll z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}
bool le(ll a , ll b , ll c , ll &x , ll &y) {
    ll d = exgcd(a , b , x , y);
    if (c % d) return 0;
    ll k = c / d;
    x *= k;
    y *= k;
    return 1;
}
ll bsgs(ll a , ll b , ll p) {
    std::map <ll , ll> h;
    h.clear();
    b %= p;
    ll t = sqrt(p) + 1;
    for (int i = 0 ; i < t ; i++) {
        ll v = b * qpow(a , i , p) % p;
        h[v] = i;
    }
    a = qpow(a , t , p);
    if (a == 0) return (b == 0) ? 1 : -1;
    for (int i = 0 ; i <= t ; i++) {
        int v = qpow(a , i , p);
        int j = h.find(v) == h.end() ? -1 : h[v];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}
ll n , y , z , k , m , x , flag , p;
int main() {
    scanf("%lld%lld" , &n , &flag);
    for (int i = 1 ; i <= n ; i++) {
        scanf("%lld%lld%lld" , &y , &z , &p);
        if (flag == 1) {
            printf("%lld" , qpow(y , z , p));
        }
        if (flag == 2) {
            if (le(y , p , z , x , m)) {
                printf("%lld" , (x % p + p) % p);
            }
            else {
                printf("Orz, I cannot find x!");
            }
        }
        if (flag == 3) {
            if (bsgs(y , z , p) == -1) {
                printf("Orz, I cannot find x!");
            }
            else {
                printf("%lld" , bsgs(y , z , p));
            }
        }
        puts("");
    }
}