というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。記号 メビウス関数 命題Pに対してをPが真なら1、偽なら0とする(アイバーソンの記法 - Wikipedia) やりたいこと がある。を求める。 例えばf=1 のときは実質totient sum ■ O(N) 約数包除 主張 fが次の3条件を満たすとき、F(N)はO(N)で計算できる。 あるが存在して任意の(d,x,y)でが成り立つ。 任意のnでがO(1)で計算できる (gcdの条件がない)について、 の列挙がO(N) 証明 実はが成り立つ。メビウス関数はディリクレ積の意味でゼータ関…