题目描述
你被要求设计一个计算器完成以下三项任务：
- 给定 (y,z,p)，计算 (y^z mod p) 的值；
- 给定 (y,z,p)，计算满足 (xy equiv z pmod p) 的最小非负整数 (x)；
- 给定 (y,z,p)，计算满足 (y^x equiv z pmod p) 的最小非负整数 (x)。
为了拿到奖品，全力以赴吧！
Analysis
模板大融合...
第一问就是一个快速幂，第二问就是线性同余方程比较基础的东西这里就不再赘述。
我们主要来看第三问怎么做（其实就是bsgs的模板）。
根据费马小定理有(y^{p-1} equiv 1 pmod p)，所以这东西是有循环节的。所以只要O(p-1)扫一遍判断就行
这里介绍一种更高效的算法：Baby-Step-Giant-Step(北上广深大步小步算法)，可以优化到(O(sqrt{p}))。
看到这个复杂度可能不少对分块熟悉的同学已经可以yy出做法了，其实bsgs就是用分块的思想。
先取一个(t)，可得(x=qt+r, 0 le r le t-1)，得到(y^{qt+r} equiv z pmod p)，这样写不舒服，换一种写法：(y^{(q+1)t - r'} equiv z pmod p)，即(y^{(q+1)t} equiv z imes y^{r'} mod p)。
先预处理出所有(b imes y^{r'})，当然尽量取更大的(r')然后枚举(q)即可。显然(t=sqrt{n})时最好。
下面给出这道题的代码，注意部分特判：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
ll y, z, p;
ll ksm(ll a, ll b, ll m) {
ll ret = 1;
while (b) {
if (b & 1) ret = (ret * a) % m;
b = b >> 1;
a = (a * a) % m;
}
return ret;
}
ll exgcd(ll a, ll b, ll &x, ll &yy) {
if (b == 0) {
x = 1;
yy = 0;
return a;
}
ll g = exgcd(b, a % b, x, yy);
ll tmp = x;
x = yy;
yy = tmp - a / b * yy;
return g;
}
//计算 a^x=b(mod n)
ll BSGS(ll a, ll b, ll n) {
a %= n;
b %= n;
if (a == 0) return b == 0 ? 1 : -1;
if (b == 1) return 0;
ll t = sqrt(n) + 1;
map<ll, ll> Hash;
Hash.clear();
for (int i = 0; i < t; i++) {
ll val = b * ksm(a, i, n) % n;
Hash[val] = i;
}
a = ksm(a, t, n);
for (int i = 1; i <= t; i++) {
ll now = ksm(a, i, n);
if (Hash.find(now) != Hash.end()) now = Hash[now];
else now = -1;
if (now != -1) return i * t - now;
}
return -1;
}
int main() {
int t, k;
cin >> t >> k;
while (t--) {
cin >> y >> z >> p;
if (k == 1) {
cout << ksm(y, z, p) << "
";
} else if (k == 2) {
ll x0, y0;
ll g = exgcd(y, p, x0, y0);
if (z % g) {
puts("Orz, I cannot find x!");
} else {
x0 = x0 * z / g;
p = p / g;
x0 = (x0 % p + p) % p;
cout << x0 << "
";
}
} else {
ll ans = BSGS(y, z, p);
if (ans != -1) cout << ans << "
";
else puts("Orz, I cannot find x!");
}
}
return 0;
}