Advertisement
ismaeil

Random Number Generator

Apr 3rd, 2022
1,041
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. ll MOD;
  6.  
  7. ll _powMod(ll n ,ll p)
  8. {
  9.     n %= MOD;
  10.  
  11.     ll x = 1;
  12.     while( p > 0 )
  13.     {
  14.         if( p & 1 ) x = (x * n) % MOD;
  15.         n = (n * n) % MOD;
  16.         p >>= 1;
  17.     }
  18.  
  19.     return x;
  20. }
  21.  
  22. ll extEuclid(ll a, ll b, ll &x, ll &y)
  23. {
  24.     ll xx = y = 0;
  25.     ll yy = x = 1;
  26.  
  27.     while( b )
  28.     {
  29.         ll q = a / b;
  30.         ll t = b; b = a % b; a = t;
  31.         t = xx; xx = x-q*xx; x = t;
  32.         t = yy; yy = y-q*yy; y = t;
  33.     }
  34.  
  35.     return a;
  36. }
  37.  
  38. ll modInverse(ll b)
  39. {
  40.     ll x ,y;
  41.    
  42.     if( extEuclid(b ,MOD ,x ,y) != 1 ) return -1;
  43.    
  44.     return (x % MOD + MOD) % MOD;
  45. }
  46.  
  47. ll solve(ll a, ll b, ll m)
  48. {
  49.     a %= m, b %= m;
  50.     ll k = 1, add = 0, g;
  51.    
  52.     while ((g = gcd(a, m)) > 1)
  53.     {
  54.         if (b == k)
  55.             return add;
  56.         if (b % g)
  57.             return -1;
  58.         b /= g, m /= g, ++add;
  59.         k = (k * 1ll * a / g) % m;
  60.     }
  61.  
  62.     ll n = sqrt(m) + 1;
  63.     ll an = 1;
  64.     for (ll i = 0; i < n; ++i)
  65.         an = (an * 1ll * a) % m;
  66.  
  67.     unordered_map<ll, ll> vals;
  68.     for (ll q = 0, cur = b; q <= n; ++q) {
  69.         vals[cur] = q;
  70.         cur = (cur * 1ll * a) % m;
  71.     }
  72.  
  73.     for (ll p = 1, cur = k; p <= n; ++p) {
  74.         cur = (cur * 1ll * an) % m;
  75.         if (vals.count(cur)) {
  76.             ll ans = n * p - vals[cur] + add;
  77.             return ans;
  78.         }
  79.     }
  80.     return -1;
  81. }
  82.  
  83. int main()
  84. {
  85.     ll a ,b ,X0 ,Xn;
  86.     scanf("%lld%lld%lld%lld%lld" ,&a ,&b ,&MOD ,&X0 ,&Xn);
  87.  
  88.     if( X0 == Xn )
  89.     {
  90.         puts("YES");
  91.         return 0;
  92.     }
  93.  
  94.     ll nome = (((Xn % MOD) - (a * Xn % MOD) + MOD) % MOD - (b % MOD) + MOD) % MOD;
  95.     ll deno = (((X0 % MOD) - (a * X0 % MOD) + MOD) % MOD - (b % MOD) + MOD) % MOD;
  96.  
  97.     if( solve(a ,nome * modInverse(deno) % MOD ,MOD) == -1 ){
  98.         puts("NO");
  99.     } else {
  100.         puts("YES");
  101.     }
  102.  
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement