totient function って何だろうと思ったら、Eulerのφ関数のことだった。Φ関数は公式をそのまま実装できるけど、m,n が互いに素のとき、Φ(mn) = Φ(m)Φ(n) という性質を利用して DP するのが速い。
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。