Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int solve(int a, int b, int m) {
- a %= m, b %= m;
- int k = 1, add = 0, g;
- while ((g = gcd(a, m)) > 1) {
- if (b == k)
- return add;
- if (b % g)
- return -1;
- b /= g, m /= g, ++add;
- k = (k * 1ll * a / g) % m;
- }
- int n = sqrt(m) + 1;
- int an = 1;
- for (int i = 0; i < n; ++i)
- an = (an * 1ll * a) % m;
- unordered_map<int, int> vals;
- for (int q = 0, cur = b; q <= n; ++q) {
- vals[cur] = q;
- cur = (cur * 1ll * a) % m;
- }
- for (int p = 1, cur = k; p <= n; ++p) {
- cur = (cur * 1ll * an) % m;
- if (vals.count(cur)) {
- int ans = n * p - vals[cur] + add;
- return ans;
- }
- }
- return -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement