积性函数
定义：对于 \(gcd(a,b)=1\)，满足 \(f(ab)=f(a)f(b)\) 的函数。
常用的积性函数：
- \(I(n) =1\)
- \(\epsilon(n) =[n==1]\)
- \(id(n)=n\)
狄利克雷卷积
对于两个数论函数 \(f,g\)，它们的狄利克雷卷积卷积是：
\[(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) \]单位元：\(f*\epsilon = f\)。
性质：
- \(μ∗I=ϵ\)，因为 \(\sum_{d|n}\mu(d)=[n==1]\)。
- \(φ∗I=id(n)\)，因为 \(\sum_{d|n}φ(d)=n\)。
- \(id∗μ=φ(n)\)。
杜教筛
如何求 \(f(i)\) 的前缀和呢？
狄利克雷卷积告诉我们，只需要构造一个积性函数 \(g(i)\)。
如果你能快速的求出 \(\sum_{i=1}^{n}(f*g)(i)\)，以及 \(\sum_{i=1}^{n}g(i)\)，就可以快速地求出 \(\sum_{i=1}^{n}f(i)\) 了。
记 \(\sum_{i=1}^{n}f(i)=S(n)\)。那么：
\[\sum_{i=1}^{n}(f*g)(i) = \sum_{i=1}^{n}\sum_{d|i}f(i)g(\frac{i}{d})=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\frac{n}{d}}f(i) =\sum_{d=1}^{n}g(d)S(\frac{n}{d})。 \]可是我们要求 \(S(n)\) 耶，令 \(d=1\) 呗。
\[S(n)=\frac{\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\frac{n}{i})}{g(1)} \]可以先线性筛出前 \(m\) 个答案，然后再用杜教筛。取 \(m =n^{\frac{2}{3}}\) 时最快。
欧拉函数
显然 \(f=\varphi,g=I,f*g=id\)。\(g\) 和 \(f*g\) 的前缀和都挺好求的。
int getphi(int n) {
if(n <= N) return sum_phi[n];
if(PHI[n]) return PHI[n];
int res = n * (n + 1) / 2;
for(int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res -= (r - l + 1) * getphi(n / l);
}
return PHI[n] = res;
}
莫比乌斯函数
显然 \(f=\mu,g=I,f*g=\epsilon\)
int getmul(int n) {
if(n <= N) return sum_mul[n];
if(MUL[n]) return MUL[n];
int res = 1;
for(int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res -= (r - l + 1) * getmul(n / l);
}
return MUL[n] = res;
}
例题：
P3768 简单的数学题
题意：
\[\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p \]分析：
使用 \(\varphi*I=id\) 解决。
\[\sum_{i=1}^{n}\sum_{j=1}^{n}ij \sum_{d|i,d|j} \varphi(d)=\sum_{d=1}^{n}\varphi(d)d^2\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}ij=\sum_{d=1}^{n}\varphi(d)d^2\frac{P^2(1+P)^2}{4} \]其中 \(P=\frac{n}{d}\)，很明显可以用整除分块来求。
考虑前面 \(\sum_{d=1}^{n}\varphi(d)d^2\) 怎么求，于是可以套用杜教筛的形式。
令 \(f(d)=\varphi(d)d^2\)，\(g(d)=d^2\)。
那么
\[(f*g)(n)=\sum_{d|n}\varphi(d)d^2\frac{n^2}{d^2}=n^3 \]\(g\) 的前缀和也很好求。
P3172 [CQOI2015] 选数
题意：
我们知道，从区间 \([L,H]\)（\(L\) 和 \(H\) 为整数）中选取 \(N\) 个整数，总共有 \((H-L+1)^N\) 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 \(N\) 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 \(K\)，你需要回答他最大公约数刚好为 \(K\) 的选取方案有多少个。
由于方案数较大，你只需要输出其除以 \(10^9+7\) 的余数即可。
分析：
令 \(L = \lceil \frac{L}{k} \rceil, R=\lfloor \frac{R}{k} \rfloor\)。
那么答案为
\[\sum_{a_1=L}^{R}\sum_{a_2=L}^{R}...\sum_{a_n=L}^{R}[gcd(a_1,a_2...a_n)==1] \]套个莫比乌斯函数
\[\sum_{a_1=L}^{R}\sum_{a_2=L}^{R}...\sum_{a_n=L}^{R}\sum_{d|a_1,d|a_2...d|a_n}\mu(d) \]把 \(d\) 放到前面去
\[\sum_{d=1}^{R}\mu(d)(\lfloor\frac{R}{d}\rfloor-\lfloor\frac{L-1}{d}\rfloor)^n \]求 \([L,R]\) 里面被 \(d\) 整除的个数相当于 \([1,R]-[1,L-1]\)。
整除分块下就好了。
标签：frac,函数,sum,varphi,杜教,学习,笔记,id From： https://www.cnblogs.com/xcs123/p/17884020.html