オイラー典型テク
思い出したら書きます
・平方根で上下に分けてDPするやつ
O(N^(3/4))になるやつ
prime countingのDPとか。全てのiについてのf(N/i)が求まる
・powerful numberの数え上げ
O(N^(1/3)loglogN)でできる
square-freeなbを用いてa^2 b^3と一意に書けるので。
・square-free numberの数え上げ
O(N^(1/2)loglogN)でできる
x が平方因子含む⇔Σ[d^2|x]μ(d)=0
x が平方因子含まない⇔Σ[d^2|x]μ(d)=1
なので（∵isqrt(x)をxの最大の平方因子の平方根として、Σ[d^2|x]μ(d)=Σ[d|isqrt(x)]μ(d)=[isqrt(x)=1]）
Σ[x≦N]Σ[d^2|x]μ(d)
=Σ[d]Σ[d^2|x≦N]μ(d)
=Σ[d≦√N]floor(N/d^2)μ(d)
floor(N/d^2)の値でまとめるテクと合わせると2/5乗になるらしい（PE193のthreadに書いてある）
・multiplicative functionの累積和
O(N^(2/3))でできる
このへん：
https://yukicoder.me/problems/no/1781
https://atcoder.jp/contests/xmascon19/tasks/xmascon19_d
Σ_{x≦N}f(x)=Σ_{x≦N}(μ*f)(x)floor(N/x)
という変形を使うこともある。この等式が成り立つことは
Σ_{x≦N}(ζ*f)(x)=Σ_{x≦N}f(x)floor(N/x)
から明らか。
μ*fがsparseだったり、累積和が計算しやすいときに使える
f=Πf_pのときμ*f=Πμ*f_pであることとあわせて使ったりもする
・multiplicative functionのDirichlet convolution
O(N^(2/3))でできる
φとかμとかσとかの累積和はこっちで解釈したほうが速い（？）
このへん：https://maspypy.com/dirichlet-%E7%A9%8D%E3%81%A8%E3%80%81%E6%95%B0%E8%AB%96%E9%96%A2%E6%95%B0%E3%81%AE%E7%B4%AF%E7%A9%8D%E5%92%8C
・60度/90度/120度をもつ三角形の列挙
前に書いた：http://hidnoblog.blog46.fc2.com/blog-entry-1529.html
以下全てn,mは互いに素を仮定
90度：
互いに素かつ和が2の倍数でないn≧m≧0により
(a,b,c)=(n^2-m^2,2nm,n^2+m^2)
60度：
互いに素かつ和が3の倍数でないn≧2m≧0により
(a,b,c)=(n^2-m^2,2nm-m^2,n^2-nm+m^2)および(n^2-m^2,n^2-2nm,n^2-nm+m^2)
120度：
互いに素かつ差が3の倍数でないn≧m≧0により
(a,b,c)=(n^2-m^2,2nm+m^2,n^2+nm+m^2)
90度の場合には実は生成行列が存在するのでこれを使うとgcdがいらないぶんlog倍早い
https://mathworld.wolfram.com/PythagoreanTriple.html
これを使うときはUを後回しにすると早い。223のthreadにあるやつをコピペして使うと簡単
・2次斉次3変数方程式の解の列挙
ピタゴラス数の列挙も「X^2+Y^2=Z^2」の解の列挙なのでこれ
・2次式の列の篩
「1≦n≦1e7のn^2+1のうち素数は何個ありますか？」みたいなやつ。
modsqrtを使ってO(NlogN)でできる
・Pell方程式
√nを連分数展開する
右辺が±1でない場合は気合で初期解を見つける必要がある。±1の解より小さいものを全探索するのが手っ取り早いがもっと賢い方法もある
このへん：https://www.alpertron.com.ar/QUAD.HTM
・分割数
オイラーの五角数定理でDPしてO(N^1.5)でできる。
全てのiについて求まる
母関数を考えるとFPSの逆元を求めてO(NlogN)でできる。
・束上のゼータ関数とメビウス関数
包除原理をいい感じにやるやつ
具体的な値はこのへん：https://ja.wikipedia.org/wiki/%E9%9A%A3%E6%8E%A5%E4%BB%A3%E6%95%B0_(%E9%A0%86%E5%BA%8F%E7%90%86%E8%AB%96)
・平方根で上下に分けてDPするやつ
O(N^(3/4))になるやつ
prime countingのDPとか。全てのiについてのf(N/i)が求まる
・powerful numberの数え上げ
O(N^(1/3)loglogN)でできる
square-freeなbを用いてa^2 b^3と一意に書けるので。
・square-free numberの数え上げ
O(N^(1/2)loglogN)でできる
x が平方因子含む⇔Σ[d^2|x]μ(d)=0
x が平方因子含まない⇔Σ[d^2|x]μ(d)=1
なので（∵isqrt(x)をxの最大の平方因子の平方根として、Σ[d^2|x]μ(d)=Σ[d|isqrt(x)]μ(d)=[isqrt(x)=1]）
Σ[x≦N]Σ[d^2|x]μ(d)
=Σ[d]Σ[d^2|x≦N]μ(d)
=Σ[d≦√N]floor(N/d^2)μ(d)
floor(N/d^2)の値でまとめるテクと合わせると2/5乗になるらしい（PE193のthreadに書いてある）
・multiplicative functionの累積和
O(N^(2/3))でできる
このへん：
https://yukicoder.me/problems/no/1781
https://atcoder.jp/contests/xmascon19/tasks/xmascon19_d
Σ_{x≦N}f(x)=Σ_{x≦N}(μ*f)(x)floor(N/x)
という変形を使うこともある。この等式が成り立つことは
Σ_{x≦N}(ζ*f)(x)=Σ_{x≦N}f(x)floor(N/x)
から明らか。
μ*fがsparseだったり、累積和が計算しやすいときに使える
f=Πf_pのときμ*f=Πμ*f_pであることとあわせて使ったりもする
・multiplicative functionのDirichlet convolution
O(N^(2/3))でできる
φとかμとかσとかの累積和はこっちで解釈したほうが速い（？）
このへん：https://maspypy.com/dirichlet-%E7%A9%8D%E3%81%A8%E3%80%81%E6%95%B0%E8%AB%96%E9%96%A2%E6%95%B0%E3%81%AE%E7%B4%AF%E7%A9%8D%E5%92%8C
・60度/90度/120度をもつ三角形の列挙
前に書いた：http://hidnoblog.blog46.fc2.com/blog-entry-1529.html
以下全てn,mは互いに素を仮定
90度：
互いに素かつ和が2の倍数でないn≧m≧0により
(a,b,c)=(n^2-m^2,2nm,n^2+m^2)
60度：
互いに素かつ和が3の倍数でないn≧2m≧0により
(a,b,c)=(n^2-m^2,2nm-m^2,n^2-nm+m^2)および(n^2-m^2,n^2-2nm,n^2-nm+m^2)
120度：
互いに素かつ差が3の倍数でないn≧m≧0により
(a,b,c)=(n^2-m^2,2nm+m^2,n^2+nm+m^2)
90度の場合には実は生成行列が存在するのでこれを使うとgcdがいらないぶんlog倍早い
https://mathworld.wolfram.com/PythagoreanTriple.html
これを使うときはUを後回しにすると早い。223のthreadにあるやつをコピペして使うと簡単
・2次斉次3変数方程式の解の列挙
ピタゴラス数の列挙も「X^2+Y^2=Z^2」の解の列挙なのでこれ
・2次式の列の篩
「1≦n≦1e7のn^2+1のうち素数は何個ありますか？」みたいなやつ。
modsqrtを使ってO(NlogN)でできる
・Pell方程式
√nを連分数展開する
右辺が±1でない場合は気合で初期解を見つける必要がある。±1の解より小さいものを全探索するのが手っ取り早いがもっと賢い方法もある
このへん：https://www.alpertron.com.ar/QUAD.HTM
・分割数
オイラーの五角数定理でDPしてO(N^1.5)でできる。
全てのiについて求まる
母関数を考えるとFPSの逆元を求めてO(NlogN)でできる。
・束上のゼータ関数とメビウス関数
包除原理をいい感じにやるやつ
具体的な値はこのへん：https://ja.wikipedia.org/wiki/%E9%9A%A3%E6%8E%A5%E4%BB%A3%E6%95%B0_(%E9%A0%86%E5%BA%8F%E7%90%86%E8%AB%96)
生きてます
コナン1000話見てたら人生が終わった
