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