用 map:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
map<ll, ll> hash;
ll p, g, t;
ll quickpow(ll a, ll b, ll p) { //快速求出a^b%p
ll res = 1ll;
a %= p;
for(; b; b >>= 1, a = a * a % p)
if(b & 1ll) res = res * a % p;
return res;
}
ll bsgs(ll a, ll b, ll p) { //求出a^x=(同余于)b(mod p)的最小的x
hash.clear();
b %= p;
ll t = (ll)sqrt(p) + 1;
for(ll j = 0; j < t; ++j) {
ll val = b * quickpow(a, j, p) % p;
hash[val] = j;
}
a = quickpow(a, t, p);
if(!a) return !b ? 1 : -1;
for(ll i = 0; i <= t; ++i) {
ll val = quickpow(a, i, p) % p;
int j = hash.find(val) == hash.end() ? -1 : hash[val];
if(j >= 0 && i * t - j >= 0) return i * t - j;
}
return -1;
}
inline ll read() {
ll f = 1ll, x = 0ll;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1ll;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10ll + c - '0';
c = getchar();
}
return x * f;
}
int main() {
g = read(), p = read(), t = read();
while(t--) {
ll A = read(), B = read();
ll a = bsgs(g, A, p);
printf("%lld\n", quickpow(B, a, p));
}
return 0;
}
用这个代码交就40分6TLE
用 unordered_map:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> cjytql;
ll p, g, t;
ll quickpow(ll a, ll b, ll p) { //快速求出a^b%p
ll res = 1ll;
a %= p;
for(; b; b >>= 1, a = a * a % p)
if(b & 1ll) res = res * a % p;
return res;
}
ll bsgs(ll a, ll b, ll p) { //求出a^x=(同余于)b(mod p)的最小的x
cjytql.clear();
b %= p;
ll t = (ll)sqrt(p) + 1;
for(ll j = 0; j < t; ++j) {
ll val = b * quickpow(a, j, p) % p;
cjytql[val] = j;
}
a = quickpow(a, t, p);
if(!a) return !b ? 1 : -1;
for(ll i = 0; i <= t; ++i) {
ll val = quickpow(a, i, p) % p;
int j = cjytql.find(val) == cjytql.end() ? -1 : cjytql[val];
if(j >= 0 && i * t - j >= 0) return i * t - j;
}
return -1;
}
inline ll read() {
ll f = 1ll, x = 0ll;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1ll;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10ll + c - '0';
c = getchar();
}
return x * f;
}
int main() {
g = read(), p = read(), t = read();
while(t--) {
ll A = read(), B = read();
ll a = bsgs(g, A, p);
printf("%lld\n", quickpow(B, a, p));
}
return 0;
}
用这个代码交就AC了?
有哪位大佬能够讲一下是怎么回事嘛qwq