オイラーのφ関数
$ \phi(n) = \text{count} \{ k | 1 \le k \le n \wedge k \perp n \}
$ nと互いに素な$ n以下の正整数の個数
式
$ n = \Pi_{p_k: \text{Prime}} {p_k}^{e_k}
に対して
$ \phi(n) = \Pi_{p_k: \text{Prime}} (p_k - 1){p_k}^{e_k - 1}
性質
$ \sum_{i = 1}^{n} \phi(n)は$ n以下の互いに素な整数のペアの個数
$ a\perp b \to \phi(ab) = \phi(a) \phi(b)(乗法的)
$ \forall a \perp m,\ a^{\phi(m)} \equiv 1 \mod m(オイラーの定理)
$ a^{\phi(m) - 1} \equiv a^{-1} \mod m
$ nの原始根は$ \phi(n)個ある(ただし、$ n=4m\ (m \gt 1), n = pq\ (p, q: \text{奇素数})のときは原始根は存在しない)
値
table:totient
n φ(n) n φ(n)
1 1 11 10
2 1 12 4
3 2 13 12
4 2 14 6
5 4 15 8
6 2 16 8
7 6 17 16
8 4 18 6
9 6 19 18
10 4 20 8
計算
素因数分解して計算
試し割り: $ O(\sqrt n)
高速素因数分解: 前処理$ O(n \log \log n)or$ O(n)(線形篩)、クエリ$ O(\log n)
ポラードロー: およそ$ O(n^{1/4})
テーブル: 前処理$ O(n \log \log n)、クエリ$ O(1)
もしかして線形篩を応用すると前処理$ O(n)でできない?