fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. const int N = 1e5 + 5;
  9. int a, n, m;
  10. int sz;
  11. pii Vec[N];
  12. int P[N], A[N];
  13. /*
  14. a ^ P ≡ a (MOD P with P is prime)
  15. a ^ (p - 1) ≡ 1 (MOD P)
  16.  
  17. a ^ C ≡ a ^ (C % (P - 1)) (MOD P);
  18.  
  19. a ^ φ(n) ≡ 1 (MOD n) với (gcd(a, n) == 1)
  20.  
  21. CRT?
  22. cần tính a || n MOD (pi ^ ki) trong ≅ O(n)
  23. */
  24. int isPrime[N], pr[N], eulerPhi[N];
  25. void sieve(int P) {
  26.     for (int i = 2; i <= P; i++) eulerPhi[i] = i;
  27.     isPrime[0] = isPrime[1] = 1;
  28.     for (int i = 2; i <= P; i++) if (!isPrime[i]) {
  29.         pr[i] = i;
  30.         for (int j = i * i; j <= P; j += i) {
  31.             isPrime[j] = 1;
  32.             pr[j] = i;
  33.         }
  34.         for (int j = i; j <= P; j += i) eulerPhi[j] -= eulerPhi[j] / i; 
  35.     }
  36. }
  37. int POW(int a, int p, int MOD) {
  38.     int ans = 1 % MOD;
  39.     a %= MOD;
  40.     for (; p; p >>= 1, a = a * a % MOD) if (p & 1) ans = ans * a % MOD;
  41.     return ans;
  42. }
  43. int inverseEulerPhi(int a, int m) {
  44.     return POW(a, eulerPhi[m] - 1, m);
  45. }
  46. void factor(int m) {
  47.     while(m > 1) {
  48.         int p = pr[m], cnt = 0;
  49.         while(m % p == 0) {
  50.             m /= p;
  51.             cnt++;
  52.         }
  53.         Vec[++sz] = {p, cnt};
  54.         P[sz] = POW(p, cnt, N); 
  55.     }
  56. }
  57.  
  58. //a ^ φ(n) ≡ 1 (MOD n) với (gcd(a, n) == 1)
  59. //a ^ C ≡ a ^ (C % (φ(n))) (MOD n);
  60. int calcCoPrime(int a, int n, int MOD) {
  61.     if (MOD == 1) return 0;
  62.     if (n == 1) return a % MOD;
  63.     int p = calcCoPrime(a, n - 1, eulerPhi[MOD]);
  64.     return POW(a, p + eulerPhi[MOD], MOD);
  65. }
  66. int getPrTimes(int a, int p) {
  67.     int cnt = 0;
  68.     while(a > 1 && a % p == 0) a /= p, cnt++;
  69.     return cnt;
  70. }
  71. int calcG(int a, int n, int MOD, int cnt, int tar) {
  72.     int C = 1;
  73.     for (int i = 1; i <= n; i++) {
  74.         if (cnt * C >= tar) return 0;
  75.         C = POW(a, C, MOD);
  76.     }
  77.     return C;
  78. }
  79. /*
  80. // Nhắc lại CRT:
  81. x ≡ a1 (mod m1)
  82. x ≡ a2 (mod m2)
  83. ...
  84. Đặt M = m1 * m2 *... mn 
  85. ⇒ x ≡ a1 * (M/m1)^φ(m1) + .. + an * (M/mn)^φ(mn) (mod M) 
  86. Hay x = (∑_{1 <= i <= n} ai * (M/mi)^φ(mi)) % M
  87. */
  88. void solve() {
  89.     sz = 0;
  90.     factor(m);
  91.     // if (__gcd(a, m) == 1) exit(1);
  92.     for (int i = 1; i <= sz; i++) {
  93.         if (a % Vec[i].ft == 0) { // GCD == 1
  94.             A[i] = calcG(a, n, P[i], getPrTimes(a, Vec[i].ft), Vec[i].sc);
  95.             // cerr << "G: " << A[i] << "\n";
  96.         }
  97.         else { // ELSE
  98.             A[i] = calcCoPrime(a, n, P[i]);
  99.             // cerr << "C: " << A[i] << "\n";
  100.         }
  101.     }
  102.  
  103.     // CRY
  104.     int ans = 0;
  105.     for (int i = 1; i <= sz; i++) {
  106.         ans = (ans + A[i] * POW(m / P[i], eulerPhi[P[i]], m)) % m;
  107.         // cerr << A[i] << " " << m / P[i] << " " << eulerPhi[P[i]] << " " << m << " -> " << A[i] << " * " << POW(m / P[i], eulerPhi[P[i]], m) << "\n";
  108.     }
  109.     cout << ans << "\n";
  110. }
  111. signed main() {
  112.     cin.tie(NULL)->sync_with_stdio(false);
  113.     if(ifstream("TETRATION.inp")) {
  114.         freopen("TETRATION.inp", "r", stdin);
  115.         freopen("TETRATION.out", "w", stdout);
  116.     }
  117.     sieve(1e5);
  118.     while(cin >> a >> n >> m) {
  119.         solve();
  120.     }
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 6112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7ci0UJ
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!