fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // #include <ext/pb_ds/tree_policy.hpp>
  4. // #include <ext/pb_ds/assoc_container.hpp>
  5. //
  6. // using namespace __gnu_pbds;
  7. // template<typename T>
  8. // using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. // #include <ext/pb_ds/assoc_container.hpp>
  10. // #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
  11. //
  12. // template<typename... Args>
  13. // void logger(string vars, Args &&... values) {
  14. //     cout << vars << " = ";
  15. //     string delim = "";
  16. //     (..., (cout << delim << values, delim = ", "));
  17. //     cout << '\n';
  18. // }
  19.  
  20. #define int long long
  21. #define ll long long
  22. #define ld long double
  23. #define nl "\n"
  24. #define aw3dni_ink_tet3aleg ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  25. #define ff first
  26. #define ss second
  27. #define all(x) x.begin(),x.end()
  28. #define sz(x) x.size()
  29.  
  30. void FILES() {
  31.     aw3dni_ink_tet3aleg
  32. #ifndef ONLINE_JUDGE
  33.     freopen("input.txt", "r", stdin);
  34.     freopen("output.txt", "w", stdout);
  35. #endif
  36. }
  37.  
  38. ll OO = 0x3f3f3f3f3f3f3f3f, oo = 0x3f3f3f3f;
  39. // const int M = 1e9 + 7, P1 = 31, P2 = 37, N = 1e5 + 5;
  40. const ld PI = 3.14159265;
  41.  
  42. // وَقُلْ رَبِّ زِدْنِي عِلْمًا
  43. struct SegmentTree {
  44.     vector<vector<int>> seg;
  45.     int size;
  46.  
  47.     SegmentTree(vector<int>& v) {
  48.         int n = sz(v);
  49.         size = 1;
  50.         while (size < n) size <<= 1;
  51.         seg.resize(size * 2);
  52.         build(0, size - 1, 0, v);
  53.     }
  54.  
  55.     void build(int l, int r, int node, vector<int>& v) {
  56.         if (l == r) {
  57.             if (l < sz(v)) seg[node] = {v[l]};
  58.             return;
  59.         }
  60.         int m = (l + r) / 2;
  61.         build(l, m, 2 * node + 1, v);
  62.         build(m + 1, r, 2 * node + 2, v);
  63.         seg[node].resize(sz(seg[2 * node + 1]) + sz(seg[2 * node + 2]));
  64.         merge(all(seg[2 * node + 1]), all(seg[2 * node + 2]), seg[node].begin());
  65.     }
  66.  
  67.     int query(int l, int r, int node, int lq, int rq, int val) {
  68.         if (rq < l || r < lq) return 0;
  69.         if (lq <= l && r <= rq) {
  70.             auto it = upper_bound(all(seg[node]), val);
  71.             return seg[node].end() - it;
  72.         }
  73.         int m = (l + r) / 2;
  74.         return query(l, m, 2 * node + 1, lq, rq, val) +
  75.                query(m + 1, r, 2 * node + 2, lq, rq, val);
  76.     }
  77.  
  78.     int query(int lq, int rq, int val) {
  79.         return query(0, size - 1, 0, lq, rq, val);
  80.     }
  81. };
  82.  
  83. int baby_stap(int a, int b, int m) {
  84.     a %= m, b %= m;
  85.     int n = sqrtl(m) + 1;
  86.     int an = 1;
  87.     for (int i = 0; i < n; ++i)
  88.         an = (an * 1ll * a) % m;
  89.     unordered_map<int, int> vals;
  90.     for (int q = 0, cur = b; q <= n; ++q) {
  91.         vals[cur] = q;
  92.         cur = (cur * 1ll * a) % m;
  93.     }
  94.     for (int p = 1, cur = 1; p <= n; ++p) {
  95.         cur = (cur * 1ll * an) % m;
  96.         if (vals.count(cur)) {
  97.             int ans = n * p - vals[cur];
  98.             return ans;
  99.         }
  100.     }
  101.     return -1;
  102. }
  103.  
  104. void solve() {
  105.     int a, b, m;
  106.     cin >> a >> b >> m;
  107.     if (m==1) {
  108.         return void(cout << 1);
  109.     }
  110.     if (a == 0) {
  111.         if (b == 1) cout << 0; // 0^0 = 1
  112.         else cout << 1; // 0^1 = 0 (b must be 0)
  113.         return;
  114.     }
  115.     cout << baby_stap(a, b, m);
  116. }
  117.  
  118. signed main() {
  119.     FILES();
  120.     int T = 1;
  121.     // seive();
  122.     // pre_count();
  123.     cin >> T;
  124.     while (T--) {
  125.         solve();
  126.         cout << nl;
  127.     }
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/vkXnL4
language:
C++ (gcc 8.3)
created:
12 hours 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!