# Random Number Generator

Apr 3rd, 2022
1,085
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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)
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. }