アルゴリズムとデータ構造8 - 線形篩による一般乗法関数の計算
概要
競技プログラミングの問題を解く中で、線形篩を用いた一般乗法関数の計算方法を学んだので、その説明を行う。
前提知識
乗法的関数：任意の互いに素な整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
完全乗法的関数：任意の整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
線形篩：O(n)でn以下の素数を列挙するアルゴリズム。
適用範囲
任意の素数pに対して、f(p)およ ...
6月10日 19:05 投稿