你被要求设计一个计算器完成以下三项任务：
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。
为了拿到奖品，全力以赴吧！
思路：
对于询问1，快速幂解决
对于询问2，扩展欧几里得解决
对于询问3，采用BSGS算法
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p, a, b; ll qmul(ll a, ll b, ll mod) { ll ans = 0; while (b) { if (b & 1) { ans = (ans + a) % mod; } a = (a + a) % mod; b >>= 1; } return ans % mod; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1; } return ans % mod; } ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } else { ll d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } } ll bsgs(ll a, ll b, ll p) { b%=p;a%=p; ll n = sqrt(p) + 1; map<ll,ll> mp; mp.clear(); ll ans = b%p; if (a == 0 && b == 0) return 0; if (a == 0 && b != 0) return -1; for (int i = 0; i <= n; i++) { mp[ans] = i; ans = qmul(ans, a, p); } ans = 1; for (int i = 1; i <= n; i++) ans = qmul(ans, a, p); ll ret = 1; for (int i = 1; i <= n; i++) { ret = qmul(ret, ans, p); if (mp[ret] != 0) { return (ll)i * n - mp[ret]; } } return -1; } int main() { int n, opt; ll a, b, p, x, y; while (scanf("%d%d", &n, &opt) != EOF) { for (int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &a, &b, &p); if (opt == 1) { printf("%lld\n", qpow(a, b, p)); } else if (opt == 2) { ll d = exgcd(a, p, x, y); if (b % d != 0) { printf("Orz, I cannot find x!\n"); } else { x = qpow(a, p - 2, p) * b % p; printf("%lld\n", x); } } else { ll ans = bsgs(a, b, p); if (ans == -1) { printf("Orz, I cannot find x!\n"); } else { printf("%lld\n", ans); } } } } return 0; }
