2007-06-26 Φ Math totient function って何だろうと思ったら、Eulerのφ関数のことだった。Φ関数は公式をそのまま実装できるけど、m,n が互いに素のとき、Φ(mn) = Φ(m)Φ(n) という性質を利用して DP するのが速い。