blob: d9227b975538bb848c5691814f7ea31274d60991 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
ll dlog(ll a, ll b, ll m) {
ll bound = sqrtl(m) + 1; //memory usage bound
map<ll, ll> vals;
for (ll i = 0, e = 1; i < bound; i++, e = (e * a) % m) {
vals[e] = i;
}
ll fact = powMod(a, m - bound - 1, m);
for (ll i = 0; i < m; i += bound, b = (b * fact) % m) {
if (vals.count(b)) {
return i + vals[b];
}}
return -1;
}
|
