\(claim\)
- \(* \rightarrow\) 狄利克雷卷积
- \((a, b) \rightarrow gcd(a,b)\)
欧拉函数
-
\(\varphi(p^k) = p ^ k - p ^ {k - 1}\)
-
\(n = \sum_{d|n} \varphi(d)\)
-
\(\varphi(n) = n \times \prod(1 - \frac{1}{p_i})\)
-
\(\varphi(nm)\varphi((n,m)) = \varphi(n)\varphi(m)(n,m)\)
杜教筛
求积性函数 \(\sum_{i=1}^n f(i)\)
设原式 = \(S(n)\)
找到一个积性函数 \(g \rightarrow\) 区间 \(sum\) 好求，\(\sum_{i=1}^nf(i)*g(i)\) 好求
\(\sum_{i=1}^n f*g(i) = \sum_{i=1}^{n}g(i)S(\frac{n}{i})\)
那么 \(g(1)S(n) = \sum_{i=1}^n f*g(i) - \sum_{i=2}^{n}g(i)S(\frac{n}{i})\)
后面整除分块递归求
标签：筛子,frac,函数,sum,varphi,好求,rightarrow From： https://www.cnblogs.com/gzyakioi/p/18423321