Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Tetration

コードについての説明(個人的メモ)

テトレーション $(a ↑↑ b) \% \ p$ を求めるアルゴリズム, つまり $a^{a^{a^{a^{\ldots}}}}$ ($a$ が $b$ 個続く) の $\mathbb{Z} / p \mathbb{Z}$ 上での値を求めるアルゴリズムである. ただしべき乗の演算は右結合的であることに注意.
(実装の都合上 $mod$ の値は $2^{31}$ 未満であることを仮定)

(関数)
tetration$(a, b, mod)$ : $(a ↑↑ b)\ \% mod$ を求める.

時間計算量: $\O (\sqrt{mod})$

コード

  1. unsigned int phi(unsigned int n)
  2. {
  3.     unsigned int res = n;
  4.     if(n % 2 == 0){ res = res / 2; do{ n /= 2; }while(n % 2 == 0); }
  5.     if(n % 3 == 0){ res = res / 3 * 2; do{ n /= 3; }while(n % 3 == 0); }
  6.     for(unsigned int i = 5; i * i <= n; i += 4){
  7.         if(n % i == 0){
  8.             res = res / i * (i - 1);
  9.             do{ n /= i; }while(n % i == 0);
  10.         }
  11.         i += 2;
  12.         if(n % i == 0){
  13.             res = res / i * (i - 1);
  14.             do{ n /= i; }while(n % i == 0);
  15.         }
  16.     }
  17.     if(n != 1) res = res / n * (n - 1);
  18.     return res;
  19. }
  20.  
  21. unsigned int mod_pow(unsigned long long a, unsigned int b, unsigned int mod, bool flag)
  22. {
  23.     unsigned long long res = 1;
  24.     while(b){
  25.         if(b & 1){
  26.             // Note: condition is true if a >= mod and flag = false
  27.             if((res *= a) >= mod) res %= mod, flag = true;
  28.         }
  29.         if((a *= a) >= mod) a = a % mod + mod;
  30.         b >>= 1;
  31.     }
  32.     return res + (flag ? mod : 0);
  33. }
  34.  
  35. unsigned int rec(unsigned int a, unsigned int b, unsigned int mod)
  36. {
  37.     if(b == 2) return mod_pow(a, a, mod, false);
  38.     const unsigned int phi_val = phi(mod);
  39.     const unsigned int res = ((phi_val == 1) ? 1 : rec(a, b - 1, phi_val));
  40.     return mod_pow(a, res, mod, (res >= phi_val));
  41. }
  42.  
  43. unsigned int tetration(unsigned int a, unsigned int b, unsigned int mod)
  44. {
  45.     if(mod == 1) return 0;
  46.     if(a == 0) return !(b & 1);
  47.     if(a == 1 || b == 0) return 1;
  48.     if(b == 1) return (a >= mod) ? (a % mod) : a;
  49.     const unsigned int res = rec(a, b, mod);
  50.     return (res >= mod) ? (res - mod) : res;
  51. }

verify 用の問題

Atcoder : 冪冪ゲーム (Powerful Fever!) 提出コード
yosupo さんの library checker : Tetration Mod 提出コード