fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. // baby step - giant step
  8. // returns minimum integer x such that a^x = b (mod m)
  9. // a and m are co-prime
  10. int discrete_log(int a, int b, int m) {
  11.   static const int inf = 2e9;
  12.   int n = (int) sqrt (m + .0) + 1;
  13.   int pw = 1;
  14.   for (int i = 0; i < n; ++i) pw = 1LL * pw * a % m;
  15.   gp_hash_table<int, int> vals;
  16.   for (int p = 1, cur = pw; p <= n; ++p) {
  17.     if (!vals[cur]) vals[cur] = p;
  18.     cur = 1LL * cur * pw % m;
  19.   }
  20.   int ans = inf;
  21.   for (int q = 0, cur = b; q <= n; ++q) {
  22.     if (vals.find(cur) != vals.end()) {
  23.       long long nw = 1LL * vals[cur] * n - q;
  24.       if (nw < ans) ans = nw;
  25.     }
  26.     cur = (1LL * cur * a) % m;
  27.   }
  28.   if (ans == inf) ans = -1;
  29.   return ans;
  30. }
  31. using ll = long long;
  32. ll extended_euclid(ll a, ll b, ll &x, ll &y) {
  33.   if (b == 0) {
  34.     x = 1; y = 0;
  35.     return a;
  36.   }
  37.   ll x1, y1;
  38.   ll d = extended_euclid(b, a % b, x1, y1);
  39.   x = y1;
  40.   y = x1 - y1 * (a / b);
  41.   return d;
  42. }
  43. ll inverse(ll a, ll m) {
  44.   ll x, y;
  45.   ll g = extended_euclid(a, m, x, y);
  46.   if (g != 1) return -1;
  47.   return (x % m + m) % m;
  48. }
  49. // discrete log but a and m may not be co-prime
  50. int discrete_log_noncoprime(int a, int b, int m) {
  51.   if (m == 1) return 0;
  52.   if (b == 1) return 0;
  53.   if (__gcd(a, m) == 1) return discrete_log(a, b, m);
  54.   int g = __gcd(a, m);
  55.   if (b % g != 0)  return -1;
  56.   int p = inverse(a / g, m / g);
  57.   int nw = discrete_log_noncoprime(a, 1LL * b / g * p % (m / g), m / g);
  58.   if (nw == -1) return -1;
  59.   return nw + 1;
  60. }
  61. int32_t main() {
  62.   ios_base::sync_with_stdio(0);
  63.   cin.tie(0);
  64.   int t = 1000;
  65.   while (t--) {
  66.     int m = rand() % 100000 + 2, a = rand() % m + 1, b = rand() % m;
  67.     cout << discrete_log_noncoprime(a, b, m) << '\n';
  68.   }
  69.   return 0;
  70. }
Success #stdin #stdout 0.02s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
-1
15765
-1
-1
-1
2816
-1
-1
-1
558
-1
-1
-1
-1
-1
-1
-1
-1
692
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3455
5014
-1
-1
-1
-1
188
-1
-1
-1
-1
-1
-1
-1
-1
5327
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
13285
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1619
-1
-1
-1
348
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
33075
-1
-1
1185
58
-1
-1
-1
-1
-1
-1
-1
-1
5917
-1
-1
-1
-1
-1
-1
-1
-1
-1
4671
-1
-1
2624
-1
-1
-1
-1
-1
5663
-1
-1
-1
-1
206
-1
-1
91280
1228
-1
-1
-1
-1
-1
16971
-1
-1
-1
10012
-1
1392
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
12493
-1
-1
-1
-1
3649
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4044
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
868
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
464
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
6018
-1
-1
-1
-1
4177
-1
10589
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
5406
183
14512
-1
18529
-1
-1
-1
-1
-1
-1
-1
-1
1886
-1
-1
-1
-1
-1
-1
-1
-1
392
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
19406
3699
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4763
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2248
-1
-1
-1
-1
-1
-1
-1
-1
-1
12242
1138
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
41241
-1
-1
-1
1685
-1
-1
-1
-1
-1
10031
-1
-1
-1
-1
-1
-1
-1
-1
-1
707
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
5375
-1
7023
-1
-1
-1
-1
139
-1
-1
-1
11551
-1
-1
-1
-1
3418
-1
11937
-1
-1
-1
767
-1
17690
1604
-1
-1
277
-1
-1
-1
-1
-1
-1
-1
-1
72747
-1
-1
-1
-1
-1
29571
-1
443
-1
-1
-1
-1
-1
6708
-1
-1
678
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
15732
-1
-1
-1
-1
9314
-1
-1
-1
-1
-1
-1
6428
1821
-1
-1
-1
-1
-1
-1
-1
-1
35758
-1
-1
4064
-1
-1
-1
-1
-1
9030
-1
-1
-1
-1
-1
7498
7896
-1
-1
-1
14280
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
59
-1
-1
-1
-1
-1
-1
18014
-1
-1
-1
-1
-1
-1
-1
7547
-1
-1
-1
-1
18264
-1
202
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
13202
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
43609
-1
-1
-1
-1
585
-1
-1
-1
6056
-1
-1
-1
-1
-1
18712
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
17904
-1
-1
-1
-1
-1
-1
-1
-1
433
-1
-1
-1
-1
-1
536
-1
-1
-1
-1
67032
-1
-1
3347
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2265
-1
-1
-1
-1
-1
33023
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
29825
-1
-1
2522
-1
2005
-1
-1
22493
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2999
-1
-1
-1
-1
-1
-1
-1
293
-1
-1
6632
-1
23669
-1
-1
-1
-1
-1
-1
-1
3694
-1
-1
-1
5295
-1
-1
17204
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2735
10586
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
9123
-1
-1
-1
34496
-1
-1
-1
-1
-1
-1
2227
-1
-1
-1
-1
-1
-1
-1
-1
-1
12078
-1
-1
-1
-1
-1
-1
-1
-1
-1
390
-1
-1
-1
-1
222
-1
-1
-1
987
246
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
955
-1
-1
-1
-1
-1
424
-1
-1
-1
-1
-1
-1
-1
-1
3247
-1
-1
-1
-1
-1
-1
145
-1
-1
21386
44712
-1
-1
-1
-1
-1
-1
8304
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
5675
13432
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
11832
-1
-1
-1
-1
39911
1513
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
8031
37561
-1
232
211
-1
-1
8010
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
34824
-1
-1
-1
-1
-1
3197
-1
33579
-1
-1
-1
-1
6597
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1742
-1
-1
6137
-1
-1
-1
-1
-1
-1
341
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2456
-1
2419
-1
https://ideone.com/6W2iSk
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!