(s_1(n)=sumlimits_{i=1}^{n}i=frac{1}{2}n(n+1) \ s_2(n)=sumlimits_{i=1}^{n}i^2=frac{1}{6}n(n+1)(2n+1)\ s_3(n)=sumlimits_{i=1}^{n}i^3=frac{1}{4}n^2(n+1)^2)
注意 (sumlimits_{d|n}=sumlimits_{d=1}^n[d|n]) ，下面经常用这个公式。
除数函数 (sigma_k(n)) n的因子的k次方和，k=0就是因子个数，k=1就是因子求和。
除数函数的前缀和，都是直接分块就可以求出来的
(f(n)=sigma_k(n)cdot n) 的前缀和（普通的乘法）
(sumlimits_{i=1}^n f(n)=sumlimits_{i=1}^n i sumlimits_{d=1}^{n}d^k[d|i]=sumlimits_{d=1}^n d^k sumlimits_{i=1}^{n}i[d|i]) ，易知 (sumlimits_{i=1}^{n}i[d|i]) 事实上就是d的所有倍数的求和，即 (dcdot s_1(lfloorfrac{n}{d}
floor))
(f(n)=varphi(n)cdot n) 的前缀和（普通的乘法）
考虑把 (f) 卷上某个函数 (g) ，使得他们的狄利克雷卷积的前缀和好求，即 ((f*g)(n)=sumlimits_{d|n}f(d)cdot g(frac{n}{d})) 的前缀和好求，展开得
((f*g)(n)=sumlimits_{d|n}f(d)cdot g(frac{n}{d})=sumlimits_{d|n}varphi(d)cdot d cdot g(frac{n}{d})) ，易知取 (g(n)=n) ，可以得到 ((f*g)(n)=sumlimits_{d|n}varphi(d)cdot n=nsumlimits_{d|n}varphi(d)=n^2) ，一般来说，一个数论函数普通乘以x个id，那么就卷上x个id把这些id全部消掉，变成数论函数与常数1的狄利克雷卷积。
其他常见求和
n以内与n互质的数的k次方和 (sumlimits_{i=1}^{n}[gcd(i,n)=1]i^k=sumlimits_{d|n}d^kmu(d)sumlimits_{i=1}^{frac{n}{d}}i^k)
当 k=0 时 (sumlimits_{d|n}mu(d)sumlimits_{i=1}^{frac{n}{d}}1=sumlimits_{d|n}mu(d)frac{n}{d}=varphi(n)) （ (mucdot I = varphi) ）
当 k=1 时 (sumlimits_{d|n}dmu(d)sumlimits_{i=1}^{frac{n}{d}}i=frac{1}{2}[n=1]+frac{1}{2}nvarphi(n))
经典问题1：gcd等于k的pair的数量。求 (f(k,n,m)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[gcd(i,j)=k])
记 (N=min(n,m)) ，则 (f(k,n,m)=sumlimits_{d=1}^{lfloorfrac{N}{k} floor}mu(d)lfloorfrac{n}{kd} floorlfloorfrac{m}{kd} floor) ，后面套个二维分块，前面用杜教筛求个前缀和。
经典问题2：gcd的k次方和。求 (f(k,n,m)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}gcd^k(i,j))
枚举gcd的值 (f(k,n,m)=sumlimits_{g=1}^{N}sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[gcd(i,j)=g]g^k) 再套上面的公式。
记 (N=min(n,m)) ，则 (f(k,n,m)=sumlimits_{g=1}^{N}g^ksumlimits_{d=1}^{lfloorfrac{N}{k} floor}mu(d)lfloorfrac{n}{kd} floorlfloorfrac{m}{kd} floor) ，后面套个二维分块，前面用杜教筛求个前缀和。
51nod1188 最大公约数之和 V2
51nod1188 最大公约数之和 V3
经典问题3：gcd为1的pair的数量。求 (f(n)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}[gcd(i,j)=1]) ，由于这里两个上界一样，变成用欧拉函数可以求
经典问题4：gcd为质数的pair的数量。求 (f(n,m)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[gcd(i,j)in primes])
可以枚举质数 (p) 转换为经典问题1，但是复杂度会很高。
https://www.luogu.com.cn/problem/P2568
https://www.luogu.com.cn/problem/P2257
(f(n,m)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[gcd(i,j)in primes]=sumlimits_{T=1}^{N}lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floorsumlimits_{p|T,pin primes}mu(frac{T}{p}))