Tetration
(Mylib/Number/tetration.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

• https://kopricky.github.io/code/Computation_Advanced/tetration.html

Depends on

• Euler's totient function (Mylib/Number/Totient/totient.cpp)

Verified with

• test/yosupo-judge/tetration_mod/main.test.cpp

Code

#pragma once
#include "Mylib/Number/Totient/totient.cpp"

namespace haar_lib {
  namespace tetration_impl {
    int rec(int64_t a, int64_t b, int64_t m) {
      if (b == 1) return a % m;
      if (b == 0) return 1 % m;
      if (b == 2) {
        bool c      = a >= m;
        int64_t ret = 1;
        int64_t p   = a;
        a %= m;

        while (p > 0) {
          if (p & 1)
            if ((ret *= a) >= m) ret %= m, c = true;
          if ((a *= a) >= m) a %= m, c = true;
          p >>= 1;
        }

        if (c) ret += m;
        return ret;
      }
      if (a == 0) return b % 2 == 1 ? 0 : 1;
      if (m == 1) return 1;

      int phi = totient(m);
      int p   = rec(a, b - 1, phi);

      bool c      = p >= phi;
      int64_t ret = 1;

      while (p > 0) {
        if (p & 1)
          if ((ret *= a) >= m) ret %= m, c = true;
        if ((a *= a) >= m) a %= m, c = true;
        p >>= 1;
      }

      if (c) ret += m;
      return ret;
    }
  }  // namespace tetration_impl

  int tetration(int64_t a, int64_t b, int64_t m) {
    return tetration_impl::rec(a, b, m) % m;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Totient/totient.cpp"
#include <cstdint>

namespace haar_lib {
  constexpr int64_t totient(int64_t n) {
    int64_t ret = n;

    for (int64_t i = 2; i * i <= n; ++i) {
      if (n % i == 0) {
        ret -= ret / i;
        while (n % i == 0) n /= i;
      }
    }

    if (n != 1) ret -= ret / n;

    return ret;
  }
}  // namespace haar_lib
#line 3 "Mylib/Number/tetration.cpp"

namespace haar_lib {
  namespace tetration_impl {
    int rec(int64_t a, int64_t b, int64_t m) {
      if (b == 1) return a % m;
      if (b == 0) return 1 % m;
      if (b == 2) {
        bool c      = a >= m;
        int64_t ret = 1;
        int64_t p   = a;
        a %= m;

        while (p > 0) {
          if (p & 1)
            if ((ret *= a) >= m) ret %= m, c = true;
          if ((a *= a) >= m) a %= m, c = true;
          p >>= 1;
        }

        if (c) ret += m;
        return ret;
      }
      if (a == 0) return b % 2 == 1 ? 0 : 1;
      if (m == 1) return 1;

      int phi = totient(m);
      int p   = rec(a, b - 1, phi);

      bool c      = p >= phi;
      int64_t ret = 1;

      while (p > 0) {
        if (p & 1)
          if ((ret *= a) >= m) ret %= m, c = true;
        if ((a *= a) >= m) a %= m, c = true;
        p >>= 1;
      }

      if (c) ret += m;
      return ret;
    }
  }  // namespace tetration_impl

  int tetration(int64_t a, int64_t b, int64_t m) {
    return tetration_impl::rec(a, b, m) % m;
  }
}  // namespace haar_lib

Back to top page