haar_lib/math/
tetration.rs

1//! $a \uparrow \uparrow b \pmod m$
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/tetration_mod>
5use crate::math::{mod_ops::pow::mod_pow, totient::totient};
6
7/// $a \uparrow \uparrow b \pmod m$を求める。
8pub fn tetration(a: u64, b: u64, m: u64) -> u64 {
9    rec(a, b, m) % m
10}
11
12fn rec(a: u64, b: u64, m: u64) -> u64 {
13    match b {
14        0 => 1 % m,
15        1 => a % m,
16        2 => mod_pow(a, a, m),
17        _ if a == 0 => 1 - b % 2,
18        _ if m == 1 => 1,
19        _ => {
20            let phi = totient(m);
21            let mut p = rec(a, b - 1, phi);
22
23            if p == 0 {
24                p = phi;
25            }
26
27            mod_pow(a, p, m)
28        }
29    }
30}
haar_lib/math/tetration.rs

haar_lib/math/
tetration.rs
