- 快速幂求解第一个
- 扩展欧几里得求第二个
- 利用Baby Step Giant Step 求第三个
C++ 代码
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
typedef long long ll;
using namespace std;
int qpow(int a, int b, int p) {
int ans = 1;
while (b) {
if (b & 1) ans = (ll)ans * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return ans;
}
int baby_step(int a, int b, int p) {
map<int, int> hash; hash.clear();
b %= p;
int t = (int)sqrt(p) + 1;
for (int j = 0; j < t; j++) {
int val = (ll)b * qpow(a, j, p) % p;
hash[val] = j;
}
a = qpow(a, t, p);
if (a == 0) return b == 0 ? 1 : -1;
for (int i = 0; i <= t; i++) {
int val = qpow(a, i, p);
int j = hash.find(val) == hash.end() ? -1 : hash[val];
if (j >= 0 && i * t - j >= 0) return i * t - j;
}
return -1;
}
int exgcd(int a, int b, ll &x, ll &y) {
if (b == 0) {
x= 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int Y, Z, P, t, k;
scanf("%d%d", &t, &k);
while (t--) {
scanf("%d%d%d", &Y, &Z, &P);
if (k == 1) {
printf("%d\n", qpow(Y, Z, P));
} else if (k == 2) {
ll x, y;
int d = exgcd(Y, P, x, y);
if (Z % d != 0) {
printf("Orz, I cannot find x!\n");
} else {
x *= Z / d;
int t = P / d;
printf("%d\n", (x % t + t) % t);
}
} else {
int t = baby_step(Y, Z, P);
if (t == -1) {
printf("Orz, I cannot find x!\n");
} else {
printf("%d\n", t);
}
}
}
return 0;
}
楼主你好,网上看的baby_step都是(a^t) ^ i * a ^ j = b (mod p),然后枚举i,通过exgcd求解a^j,您这里hash表直接存的是b * a ^ j,这是什么道理啊,有点没想通。
不知道是你看错了, 还是人家的 j 是负数
$a^{i*t-j} = (a^i)^t / a^j \equiv b (mod p) $
$(a^i)^t \equiv b * a^j (mod p)$