totient_table.hpp ファイル

#include "../../kyopro_library/template.hpp"

[ソースコード]

関数
vector< ll >	TotientTable (ll n)
	オイラーのtotient関数を前計算する

関数詳解

TotientTable()

vector< ll > TotientTable

(

ll

n

)

オイラーのtotient関数を前計算する

totient(0) ... totient(n) を前計算する

覚え書き

O(n log(log(n))) https://qiita.com/drken/items/3beb679e54266f20ab63 https://manabitimes.jp/math/667

totient(i) = i 以下であって、i と互いに素な数の個数

公式: totient(n) = n * Π(1 - 1/p) (p は n の素因数)

公式: totient(n)totient(m) = totient(nm) (n と m が互いに素)

公式: Σ(d | n) totient(d) = n

公式: a^totient(m) ≡ 1 (mod m) (a と m が互いに素)

totient_table.hpp の 13 行目に定義があります。