メビウス関数

周期的なものの数え上げの時に役立ちそう。

蟻本の周期的でない文字列の数え上げを考えましょう。
周期1,2,3,4,...みたいな感じでNの約数をすべて列挙して包除原理をすれば求まりますが、約数は100コとか200コになる可能性があるのでこれでは間に合いません。
しかし、集合の要素としてありうるのはNの約数aのみであり、aが何個の集合によって囲われているかは数えることができるので、2^(約数の数)みたいな計算量は回避できます。(そもそも包除原理=O(2^N)という考え方が良くない。包除原理で大事なのは集合の重複の数)このaを含む集合の数は結局aの素因数の個数kと等しいです。そこでメビウス関数が出てきます。メビウス関数はaを引数としてkを返す関数です。O(√N)でメビウス関数の各値は求めることができるのでこれを使えば十分高速に解を求められます。

またオイラー関数とも密接な関係があります。
φ(n)=Σ(d|n) μ(n/d)*nが成立します。なので場合によってはメビウス関数を含む式を変形してオイラー関数の形にすることもできます。しかし、この式変形は結構複雑なので(蟻本に載ってる)、メビウス関数が出てきたら、オイラー関数が出てくるような考察ができないかどうか考えてみるのがいいと思います。