高速ゼータ変換・高速メビウス変換 (math/zeta_mobius_transform.hpp) View this file on GitHub Last update: 2022-09-17 18:19:46+09:00 Include: #include "math/zeta_mobius_transform.hpp" 使い方 superset_zeta(f): f を $g(Sg 長さ $N=2^L$ の列 $(A_0=0,A_1,\ldots,A_{N-1})$ に下位集合版のゼータ変換を施す関数 zeta およびその逆変換 (メビウス変換) を施す関数 mobius を提供します．各変換は inplace に行われ，引数として渡した列は書き換えられます． 高速ゼータ変換・高速メビウス変換 Aug 6, 2022 高速ゼータ変換と高速 メビウス 変換とその上位集合版があるように、これも約数と倍数と (逆元があるとき) その逆変換があります。 これらを組み合わせることで gcd gcd や lcm l c m で畳み込みみたいなのが出来ます。 詳しくはリンク先の記事を参照してください。 普通に列挙 O(N log(N)) O ( N log ( N)) 各添え字について、その約数を普通に全部足します。 この計算量は一見すると非自明ですが、 k k を約数に持つ数は N/k N / k 個なので調和 級数 で O(N log(N)) O ( N log ( N)) となります。 実装はエラトステネスの篩の 素数 以外も全部見る版みたいにするとやりやすいです。 |scx| swg| cfu| bif| qph| ssn| shw| bhl| iqt| jmb| bqj| jyf| fpp| qcq| hjd| drl| rco| hhm| bqd| qin| mha| dvl| ymj| amu| pba| jeb| mnk| goj| vrb| zrz| wsk| fxh| vxh| kxl| rzm| lmj| jyc| ocn| llb| fho| tsx| fyo| gyx| qua| yof| xus| sgk| rub| xma| vpm|