模拟赛考了一道莫反结果只写了低档暴力
定义完全积性函数：定义域在(>0)的自然数内。
有(f(ab)=f(a)f(b))
例子：(f(a)=a)
定义积性函数：如果((a,b)=1,f(ab)=f(a)f(b))
推论：设(a)的唯一分解：(p_1^{b1}p_2^{b2}...p_n^{bn})，则(f(a)=f(p_1^{b1})f(p_2^{b2})...f(p_n^{bn}))
积性函数的求法：线性筛。
在遍历所有倍数的过程中：
要求当(imod p=0)时，则(f(ip))的值能够被算出。
当(imod p
eq 0)时，按照积性函数的性质计算(f(ip))
所以线性筛法要求：在质数处次幂的取值能够快速算出，一个数和质数的乘积的函数值可以快速算出。
事实上，根据素数定理，我们只需要做(frac{n}{log_2n})次函数在质数处的求值。
这使得我们可以在几乎线性的时间内求出所有(i^k)。
常见的积性函数：定义mobius函数(u)。
它的函数值：
当(a=1)，(u(a)=1)
设(a)的唯一分解：(p_1^{b1}p_2^{b2}...p_n^{bn})
当(b_1=b_2=...=b_n=1)，则(u(a)=(-1)^n)
否则(u(a)=0)
这事实上满足上面筛法对与积性函数的约定，所以可以线性筛求出。
常见的积性函数：(p(x))表示(<x)的和(x)互质的正整数。
求法：设(a)的唯一分解：(p_1^{b1}p_2^{b2}...p_n^{bn})
则(p(x)=xprod_{i=1}^nfrac{p_i-1}{p_i})
它的性质：当(x)是质数，则(p(x)=x-1)，当(xmod p
eq 0)，(p)是素数，(p(x*p)=p(x)*(p-1))
这使得它满足线性筛的约定，可以线性筛。
数论函数(e(x)=[x=1])
数论函数(I(x)=1)
数论函数(d(x))是(x)的约数个数
数论函数(id(x)=x)
数论函数(id(x)^n=x^n)
定义两个函数的dirchlet卷积：(h(n)=sum f(frac{n}{i})g(i))记为(h=f*g)
其中(i|n)
求法：调和级数
void ml(int *a,int *b,int *ans){
for(int i=1;i<=n;i++)
for(int j=i;j*i<=n;j+=i)
ans[j]+=a[i]*b[j/i];
}
时间复杂度(O(nlog_2n))
定义两个函数互为逆元：(e=f*g)
在已知(f)的情况下，(g)可以构造出来。
方法：https://www.luogu.com.cn/paste/64fn78k9
定义dirchlet前缀和：(b(n)=sum a(frac{n}{i}))，其中(i|n)
这事实上是(b*I)
它有两种做法：
做法1：枚举(a(x))，贡献到(x)的倍数。
时间复杂度(O(nlog_2n))
做法2：魔力筛
void si(int *a){
for(int i=1;p[i]<=n;i++)
for(int j=1;j*p[i]<=n;j++)
a[j*p[i]]+=a[j];
}
(p)是素数表。
考虑(j)的唯一分解，发现事实上它是在按照质数从小到大的顺序做高维前缀和。
这就证明了它的正确性
可以证明时间复杂度是(O(nlog_2log_2n))
(b*u)也可以快速求
void si(int *a){
for(int i=ct;i;i--)
for(int j=(N-1)/p[i];j;j--)
a[j*p[i]]-=a[j];
}
事实上它是在按照质数从小到大的顺序做高维差分。
时间复杂度也是(O(nlog_2log_2n))
dirchlet卷积的常见定理：
莫比乌斯定理：(e=I*u)
事实上可以把(u)函数看成容斥原理。
如果(f,g)都是积性函数则(f*g)是积性函数
莫比乌斯反演的两种形式：
(F(n)=sum_d f(frac{n}{d}),f(n)=sum_d u(frac{n}{d})F(d)，[d|n])
证明：(F=I*f)，根据mobius反演定理(f=F*u)
(F(n)=sum_d f(d),[n|d],f(n)=sum_d u(frac{d}{n})F(d),[n|d])
这个不知道怎么证明
整除分块算法：用于快速求(sum_{i=1}^n lfloorfrac{n}{i}
floor)
虽然(i)的取值有(n)种，但是(lfloorfrac{n}{i}
floor)的取值只有(O(sqrt{n}))种。
可以用如下算法求出：
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
}
(lfloorfrac{n}{i}
floor)和(i)相同的范围是([i,j])。
这是基于一个结论：和(i)整除性相同的最大位置是(lfloorfrac{n}{lfloorfrac{n}{i}
floor}
floor)
即使把(i)换成其他的值也能做。
如果有多个下取整，可以取(min)
如果我们要求(sum_{i=1}^n lfloorfrac{n}{i}
floor f(i))，则事实上我们要对于每个(lfloorfrac{n}{i}
floor f(i))的取值(d)，求出(df(i))的和。
这相当于求出(f(i))在区间([i,j])的和。
差分后就变成前缀和。
所以我们需要求出(f(i))的前缀和。
杜教筛：
用于计算某个积性函数(g)的前缀和
考虑构造另一函数(f)，计算(f*g)的前缀和。
设(S(n))是(g)从(1 o n)的前缀和
(sum_{i=1}^nsum_{d|i}f(d)g(frac{i}{d}))
(=sum_{d=1}^nf(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}g(i))
(=sum_{d=1}^nf(d)S(lfloorfrac{n}{d}
floor))
考虑差分
(f(1)S(n)=sum_{d=1}^nf(d)S(lfloorfrac{n}{d}
floor)-sum_{d=2}^nf(d)S(lfloorfrac{n}{d}
floor)=sum_{i=1}^n(f*g)(i)-sum_{d=2}^nf(d)S(lfloorfrac{n}{d}
floor))
这样子就能快速算(S(n))了。
如果我们能够快速计算(sum_{i=1}^n(f*g)(i))也就是(f*g)的前缀和，使用整除分块快速计算(sum_{d=2}^nS(lfloorfrac{n}{d}
floor))，我们就能得到答案。
根据前面的分析，我们要快速求的事实上是(f*g)的前缀和，所以需要构造一个可以快速求前缀和的函数。
可以证明，如果用记忆化，时间复杂度为(O(n^{frac{3}{4}}))
如果预处理出前(n^{frac{2}{3}})个答案，时间复杂度为(O(n^{frac{2}{3}}))
关于数论函数的几个结论：
1.(u(ij)=u(i)u(j)[iperp j])
这事实上是积性分解
2.(d(ij)=sum_{x|i}sum_{y|j}[xperp y])
这是sdoi某题的结论
推论：(d(ijk)=sum_{x|i}sum_{y|j}sum_{z|k}[xperp y][xperp z][yperp z])
(sigma_1(ij)=sum_{x|i}sum_{y|j}[xperp y]xy)
3.(p(ij)=frac{p(i)p(j)(i,j)}{p((i,j))})
这是bzoj3152的结论。
4.([(a,b)=d]=[(frac{a}{d},frac{b}{d})=1])
5.如果(f)是积性函数，(f(gcd(a,b))f([a,b])=f(a)f(b))
6.(u(i)^2=sum_{e^2|i}u(e))
7.(sum_{i=1}^nlfloorfrac{n}{i}
floor=sum_{i=1}^nd(i))
数论反演的变换和式规则：
1.交换(sum,prod)
这样子可能可以把一个函数拿出来
2.分拆
把数论函数拆成多个部分放在(sum,prod)内
这事实上是分配律。
有时候要构造出能够分拆成两部分的函数。
如果(f(x))能够被移动到前面，则保证前面要有(f)内部的量
3.枚举每个数的出现次数
这个数要被视为整体。
对于1,3，可能有新的对于和式的限制，要小心处理
只要在满足前面三个条件，就可以任意变换。
有时候如果一个数论函数的部分太麻烦，则可以视为一个整体进行
事实上，如果无法交换和式，且和式内有比较麻烦的部分。
则可以将里面的部分构造新的函数。
数论函数(sigma(x))就是(x)的约数和，(sigma^k(x))就是(x)的所有约数的(k)次方和。
关于数论函数的几个定理：(u*I=e)
(p*I=id)
(d=I*I)
(sigma=id*I)
(sigma^k=id^k*I)
如果整除分块内有多个下取整函数，则应该在每次整除分块时，在一段内保证这些函数的值不变。
对于每个数处理出((a_i,c))，表示在([a_i,a_{i+1}))区间内值为(c)。
然后把所有的二元组按照(a)排序后计算。
快速存储(lfloorfrac{n}{i}
floor)的方法：
由于整除分块，本质不同的(lfloorfrac{n}{i}
floor)只有(sqrt{n})种。
当(lfloorfrac{n}{i}
floor)较小（小于(sqrt{n})），则存在(f_{lfloorfrac{n}{i}
floor})
否则存在(g_{lfloorfrac{lfloorfrac{n}{i}
floor}{i}
floor})内。
例题，有代表性的才有详细题解，才会写代码：
1.sub problem：
(sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d])
(sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}[gcd(i,j)=1])
(sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}sum_{e|gcd(i,j)}u(e))
(sum_{e=1}^nu(e)lfloorfrac{n}{de}
floorlfloorfrac{m}{de}
floor)
用整除分块计算
1.1 YY的GCD
用sub-problem转化原式，可以得知
(sum_{d=1}^n[d is prime]sum_{e=1}^nu(e)lfloorfrac{n}{de}
floorlfloorfrac{m}{de}
floor)
直接做会tle。
但是可以枚举(de)，枚举后发现我们要预处理(sum[t is prime]u(frac{T}{t}))
这可以用调和级数处理。
1.2 [HAOI2011]Problem b
有了关于区间的限制，可以拆成4个二维前缀和
1.3 能量采集
先把答案(-nm)后(/2)
根据1.1的经验，我们要求(sum_{T=1}^{min(n,m)}lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floorsum_{d|T}du(frac{T}{d}))
后面(sum_{d|T}du(frac{T}{d}))事实上是(u*I=p)，可以线性筛
1.4 数表
忽略对于(sigma_1)的限制
(ans=sum_{i=1}^nsum_{j=1}^msigma_0((gcd(i,j)))
用子问题的结论，枚举(gcd)，(ans=sum_{d=1}^{n}sigma_1(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}[(i,j)=1]=sum_{d=1}^{n}sigma_1(d)sum_{e=1}^{lfloorfrac{n}{d}
floor}u(e)lfloorfrac{n}{de}
floorlfloorfrac{m}{de}
floor)
枚举(T=de)，答案等于(sum_{T=1}^nlfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floorsum_{e|T}u(frac{T}{e})sigma_1(e))
用整除分块计算(sum_{T=1}^nlfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor)，事实上我们要求一个区间的(sum_{e|T}u(frac{T}{e})sigma_1(e)[sigma_1(e)leq a])
这事实上是一个有(nsqrt{n})次插入和查询的二维偏序问题，用bit解决。
1.5 crash的数字表格
(sum_{i=1}^nsum_{j=1}^m[i,j]=sum_{i=1}^nsum_{j=1}^mfrac{ij}{gcd(i,j)}=sum_{d=1}^ndsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}[(i,j)=1]ij=sum_{d=1}^ndsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}sum_{e|(i,j)}u(e)ij)
(=sum_{d=1}^ndsum_{e=1}^{lfloorfrac{n}{d}
floor}u(e)sum_{i=1}^{lfloorfrac{n}{de}
floor}sum_{j=1}^{lfloorfrac{m}{de}
floor}ij)
(=sum_{d=1}^ndsum_{e=1}^{lfloorfrac{n}{d}
floor}u(e)s2(lfloorfrac{n}{de}
floor)s2(lfloorfrac{m}{de}
floor))
枚举(T=de)，(sum_{T=1}^ns2(lfloorfrac{n}{T}
floor)s2(lfloorfrac{m}{T}
floor)sum_{e|T}u(e)frac{T}{e})
前面(s2(lfloorfrac{n}{T}
floor)s2(lfloorfrac{m}{T}
floor))整除分块，后面就是(u*id)
发现这是积性函数，可以用线性筛求出。
1.6 lg5221
(prod_{i=1}^nprod_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}=prod_{i=1}^nprod_{j=1}^nfrac{ij}{gcd(i,j)^2}=(prod_{i=1}^nprod_{j=1}^n{ij})*(prod_{i=1}^nprod_{j=1}^nfrac{1}{gcd(i,j)})^2)
((prod_{i=1}^nprod_{j=1}^n{ij})=(prod_{i=1}^ni)(prod_{j=1}^nj)=(n!)^2)
((prod_{i=1}^nprod_{j=1}^nfrac{1}{gcd(i,j)})^2)就是sub-problem
1.7 作业题
用(p*I=id)
(sum_{T}sum_{e}(sum_{i=1}^{n-1}e_i)gcd(e_1...e_{n-1}))
(sum_{T}sum_{e}(sum_{i=1}^{n-1}e_i)sum_{d|w_{1}...d|w_{n-1}}p(d))
枚举(d)。
(sum_{d=1}^mxp(d)sum_{d|w_{1}...d|w_{n-1}}sum_{e}(sum_{i=1}^{n-1}e_i))
这事实上可以对于每个(d)，提取出(d)的倍数进行矩阵树定理
把每条边(i)看做一个多项式(w_ix+1)。
在矩阵树定理中，加法就是多项式加法，乘法就是多项式乘法，除法就是多项式求逆。
注意剪枝：一个有效的剪枝：如果当前边数(<n-1)则不用矩阵树。
1.8 文艺数学题
上一道题弱化版。
1.9 选数
又是裸题
(ans=sum_{i1=L}^Hsum_{i2=L}^H....sum_{in=L}^H[gcd(i1,i2...in)=k])
令(l=lfloorfrac{L-1}{k}
floor,r=frac{H}{k})
(ans=sum_{i1=l}^rsum_{i2=l}^r....sum_{in=l}^r[gcd(i1,i2...in)=1])
莫反，(ans=sum_{i1=l}^rsum_{i2=l}^r....sum_{in=l}^rsum_{d|gcd(i1,i2...in)}u(d))
拿出(d)，(sum_{i=1}^r(lfloorfrac{R}{k}
floor-lfloorfrac{L-1}{k}
floor)^n)
杜教筛即可。
1.10 lcm
1.11 DZY Loves Math VI
(ans=sum_{i=1}^nsum_{j=1}^n(frac{ij}{gcd(i,j)})^{gcd(i,j)})
枚举(gcd)，(ans=sum_{i=1}^nsum_{j=1}^n(frac{ij}{gcd(i,j)})^{gcd(i,j)})
(ans=sum_{d=1}^nsum_{i=1}^nsum_{j=1}^n[gcd(i,j)=1](ijd)^d)
反演，(ans=sum_{d=1}^nd^dsum_{i=1}^nsum_{j=1}^nsum_{e|i,e|j}u(e)(ij)^d)
(ans=sum_{d=1}^nd^dsum_{e=1}^{lfloorfrac{n}{d}
floor}u(e)(sum_{i=1}^{lfloorfrac{n}{de}
floor}i^d)(sum_{j=1}^{lfloorfrac{n}{de}
floor}j^d))
令(f_i=i^d)，在(d)增大时，(f)可以被递推算出
算出(f)后算前缀和，(ans)就能在调和级数时间内计算。
1.12 [bzoj3309]DZY Loves Math
1.13 atoranta
https://www.cnblogs.com/ctmlpfs/p/14092130.html
2.于神之怒加强版
用1.3转化原式，可以得知
(sum_{T=1}^{min(n,m)}lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floorsum_{d^k|T}du(frac{T}{d}))
后面是(f=id^k*u)。
发现后面是积性函数。
考虑怎么求它在(p^k)的值。
后面只有当(u)取(1)或者(p)才有意义。
所以(f(p^v)=(p^k-1)p^{k(v-2)})
要求它和一个质数(p)的乘积
这样子就可以线性筛了。
根据素数定理，(log_2)被去掉了。
3.数字表格
这道题说明乘法函数也是能拆贡献的。
枚举(gcd(i,j))
根据sub-problem的结论答案是(prod_{i=1}^nf_d^{sum_{i=1}^{lfloorfrac{n}{d}
floor}u(i)lfloorfrac{n}{id}
floorlfloorfrac{m}{id}
floor})
枚举(id)
(prod_{T=1}^nprod_{d|T}f_d^{u(frac{T}{d})lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor})
对(lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor)整除分块，前面暴力预处理。
4.[SDOI2015]约数个数和
用上面提到的结论转化公式即可。
5.简单的数学题
(sum_{d=1}^ndsum_{i=1}^nsum_{j=1}^n[gcd(i,j)=d]ij)
(sum_{d=1}^nd^3sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}[gcd(i,j)=1]ij)
(sum_{d=1}^nd^3sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}sum_{e|gcd(i,j)}u(e)ij)
(sum_{d=1}^nd^3sum_{e=1}^{lfloorfrac{n}{d}
floor}u(e)e^2(sum_{i=1}^{lfloorfrac{n}{de}
floor}i)(sum_{j=1}^{lfloorfrac{n}{de}
floor}j))
(sum_{d=1}^nd^3sum_{e=1}^{lfloorfrac{n}{d}
floor}u(e)e^2s2({lfloorfrac{n}{de}
floor})^2)
枚举(de)，(sum_{T=1}^nT^2s2(lfloorfrac{n}{T}
floor)sum_{e|T}u(frac{T}{e})e)
后面是(u*id=p)
(sum_{T=1}^nT^2s2(lfloorfrac{n}{T}
floor)p(T))
筛(i^2p(i))构造(g(x)=x^2)，则两者卷积起来答案等于(x^3)，前缀和可以快速计算
6.小Q的表格
套路题
研究(f)的性质，它很像(gcd)。
容易发现，它一定会递归到((gcd(a,b),gcd(a,b)))
打表可得，(f(a,b)=frac{f(gcd(a,b),gcd(a,b))}{gcd(a,b)^2})
如果修改一个格子((a,b))，则实质上是修改(f(gcd(a,b),gcd(a,b)))，这可以快速计算。
考虑莫反，枚举(gcd(a,b))，(ans=sum_{d=1}^nf(d,d)sum_{d|i}sum_{d|j}frac{ij}{d^2}[gcd(i,j)=d])
(ans=sum_{d=1}^nf(d,d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{i=1}^{lfloorfrac{n}{d}
floor}ij[gcd(i,j)=1])
令(G(x)=sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{i=1}^{lfloorfrac{n}{d}
floor}ij[gcd(i,j)=1])
有一结论：(G(x)=sum_{i=1}^nsum_{j=1}^n[(i,j)=1]ij=sum_{i=1}^n i^2p(i))
(ans=sum_{d=1}^nf(d,d)sum_{i=1}^{lfloorfrac{n}{d}
floor} i^2p(i))
对(lfloorfrac{n}{d}
floor)，则我们要预处理(sum_{i=1}^{lfloorfrac{n}{d}
floor} i^2p(i))的前缀和，查询时要查询(O(qsqrt{n}))次区间和。
这显然能用bit维护。
由于修改的次数是(O(n))，查询的次数是(O(nsqrt{n}))，使用分块可以得到更优秀的复杂度
7.四月樱花
8.毒瘤之神的考验
由前面的结论(ans=sum_{i=1}^nsum_{j=1}^mfrac{p(i)p(j)gcd(i,j)}{p(gcd(i,j))})
拿出(gcd)，(ans=sum_{d=1}^nfrac{d}{p(d)}sum_{i=1}^nsum_{j=1}^mp(i)p(j)[gcd(i,j)=d])
(ans=sum_{d=1}^nfrac{d}{p(d)}sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}p(id)p(jd)[gcd(i,j)=1])
反演，(ans=sum_{d=1}^nfrac{d}{p(d)}sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}p(id)p(jd)sum_{e|gcd(i,j)}u(e))
拿出(e)，(ans=sum_{d=1}^nfrac{d}{p(d)}sum_{e=1}^{lfloorfrac{m}{d}
floor}u(e)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}p(ide)p(jde))
枚举(T=de)，(ans=sum_{T=1}^nsum_{d|T}(frac{d}{p(d)}u(frac{T}{d}))(sum_{i=1}^{lfloorfrac{n}{d}
floor}p(iT))(sum_{j=1}^{lfloorfrac{m}{d}
floor}p(jT)))
(G(T)=sum_{d|T}(frac{d}{p(d)}u(frac{T}{d})))可以调和级数处理
设(f(i,j)=sum_{d=1}^np(dj))，显然有(f(i,j)=f(i-1,j)+p(ij))
(f)只需要处理到(ijleq n)，值域是调和级数，是(O(nlog_2n))的
原式转化为(ans=sum_{T=1}^nG(T)f(T,lfloorfrac{n}{d}
floor)f(T,lfloorfrac{m}{d}
floor))
令(h(a,b,n)=sum_{T=1}^nG(T)f(T,a)f(T,b))，这样子就能整除分块了。
整除分块后，我们要计算一段(h(a,b,r)-h(a,b,l-1))这在当(lfloorfrac{n}{d}
floor)较小时相当优，然而较大时不能预处理
设一个阈值(B)，考虑计算(h(a,b,n),aleq B,bleq B)，可以递推
(h(a,b,n)=h(a,b,n-1)+G(n)f(n,a)f(n,b))
当(a>B)或者(b>B)时暴力计算。
时间复杂度(O(nlog_2n+nB^2+T(sqrt{n}+frac{n}{B})))
8.1 CF809E
由前面的结论(ans=sum_{i=1}^nsum_{j=1}^nfrac{p(a_i)p(a_j)gcd(a_i,a_j)}{p(gcd(a_i,a_j))}di(i,j))
显然拿出(gcd,ans=sum_{d=1}^nfrac{d}{p(d)}sum_{i=1}^nsum_{j=1}^np(a_i)p(a_j)di(i,j)[gcd(a_i,a_j)=d])
(gcd,ans=sum_{d=1}^nfrac{d}{p(d)}sum_{i=1}^nsum_{j=1}^np(a_i)p(a_j)di(i,j)[gcd(frac{a_i}{d},frac{a_j}{d})=1][a_i|d][a_j|d])
(gcd,ans=sum_{d=1}^nfrac{d}{p(d)}sum_{i=1}^nsum_{j=1}^np(a_i)p(a_j)di(i,j)sum_e[e|frac{a_i}{d},e|frac{a_j}{d}]u(e)[a_i|d][a_j|d])
拿出所有被(d)整除的数，除以(ed)，设为(b)，有(p)个，下标为(c)
(ans=sum_{d=1}^nfrac{d}{p(d)}sum_{e=1}^nu(e)sum_{i=1}^psum_{j=1}^pp(b_ied)p(b_jed)di(c_i,c_j))
枚举(T=ed)，(ans=sum_{T=1}^n(sum_{d|T}frac{d}{p(d)}u(frac{T}{d}))sum_{i=1}^psum_{j=1}^pp(b_iT)p(b_jT)di(c_i,c_j))
设(F(T)=(sum_{d|T}frac{d}{p(d)}u(frac{T}{d})))，对所有(c)建立虚树，(ans=sum_{T=1}^nF(T)sum_{i=1}^psum_{j=1}^pp(b_iT)p(b_jT)di(c_i,c_j))
由于(a)互不相同，所以虚树总点数是(O(nlog_2n))的。
设(a_i=p(Tb_i))，则我们要求(ans=sum_{T=1}^nF(T)sum_{i=1}^psum_{j=1}^pa_ia_jdi(dep_{c_i}+dep_{c_j}-dep_{lca(c_i,c_j)}))
(dep_{c_i}+dep_{c_j})显然可以考虑每个数的贡献然后直接算。
(dep_{lca(c_i,c_j)})考虑枚举(lca=x)
这就是((sum_{i=1}^pa_i)(sum_{j=1}^pa_j)dep_{x})，可以容斥计算。
9.jzpkil
套路题
(sum_{i=1}^ngcd(i,n)^x[i,n]^y=n^ysum_{i=1}^ngcd(i,n)^{x-y}i^y)
如果(x=y)，那么显然可以直接自然数幂求和
(n^ysum_{i=1}^ngcd(i,n)^{x-y}i^y=n^ysum_{d|n}d^{x-y}sum_{i=1}^n[gcd(i,n)=d]i^y)
(=n^ysum_{d|n}d^{x-y}sum_{i=1}^{lfloorfrac{n}{d}
floor}[gcd(i,frac{n}{d})=1](id)^y)
(=n^ysum_{d|n}d^xsum_{i=1}^{lfloorfrac{n}{d}
floor}i^ysum_{e}[e|i,ed|n]u(e))
(=n^ysum_{d|n}d^xsum_{ed|n}u(e)e^y(sum_{i=1}^{frac{n}{de}}i^y))
((sum_{i=1}^{lfloorfrac{n}{de}
floor}i^y))事实上是一个取值为(frac{n}{de})的最多(y)次多项式，设系数为(a)
(=n^ysum_{d|n}d^xsum_{ed|n}u(e)e^ysum_{i=0}^y(frac{n}{de})^ia_i)
事实上，这是dirchlet卷积
设(f(p)=p^x,g(p)=u(p)e^y,h(p)=sum_{i=0}^yp^ya_i)
则答案等于(f*g*h)
发现(h)不是积性函数，所以不太能做
但是把(i)拿出来，(f*g*h)就是积性函数了。
(=n^ysum_{i=0}^ya_isum_{d|n}d^xsum_{ed|n}u(e)e^y(frac{n}{de})^i)
设(f(p)=p^x,g(p)=u(p)e^y,h(p)=p^i)，这样子就是积性函数了。
根据积性函数的定义，考虑对于每个(p)，计算((f*g*h)(p^k))
枚举(p^k)的分拆，最多((log_2n)^2)种，然后暴力计算答案。
时间复杂度是(O(y(log_2n)^2+n^{frac{1}{4}}+y^2))
考虑挖掘((f*g*h)(p^k))的限制，事实上，这对于(g)的限制非常苛刻，只有当(g)中(p)的幂次取(0,1)时才有可能有值。
时间复杂度是(O(ylog_2n+n^{frac{1}{4}}+y^2))
10.时空穿梭
枚举第一个点和最后一个点的坐标差
设(mn)为(m)的最小值
(ans=sum_{x1,x2...xn}C_{gcd(x_1,x_2...x_n)}^{c-2}prod_{i=1}^n(m_i-x_i))
拿出(gcd)，(ans=sum_dC_{d}^{c-2}sum_{x1,x2...xn}prod_{i=1}^n(m_i-dx_i)[gcd(x_1...x_n)=1])
反演，得到(ans=sum_dC_{d}^{c-2}sum_{x1,x2...xnleq frac{m_i}{d}}prod_{i=1}^n(m_i-dx_i)sum_eu(e)[e|gcd(x_1...x_n)])
拿出(e)，(ans=sum_{dleq mn}C_{d}^{c-2}sum_{eleq frac{mn}{d}}u(e)sum_{x1,x2...xnleq frac{m_i}{de}}prod_{i=1}^n(m_i-dex_i))
用和式的定律转化上式，这个部分把时间复杂度降低到多项式级别，得到：(ans=sum_{dleq mn}C_{d}^{c-2}sum_{eleq frac{mn}{d}}u(e)prod_{i=1}^nsum_{x_ileq frac{m_i}{de}}(m_i-dex_i))
用等差数列求和转化后面，(ans=sum_{dleq mn}C_{d}^{c-2}sum_{eleq frac{mn}{d}}u(e)prod_{i=1}^nfrac{lfloorfrac{m_i}{de}
floor(2m_i-de-delfloorfrac{m_i}{de}
floor)}{2})
枚举(T=de)，(ans=sum_{T=1}^{mn}(prod_{i=1}^nfrac{lfloorfrac{m_i}{T}
floor(2m_i-T-Tlfloorfrac{m_i}{T}
floor)}{2})(sum_{d|T}C_{d-1}^{C-2}u(frac{T}{d})))
用调和级数枚举倍数预处理(sum_{d|T}C_{d-1}^{c-2}u(frac{T}{d}))，设为(f(T))
拿出(T)，(ans=sum_{T=1}^{mn}(prod_{i=1}^nfrac{lfloorfrac{m_i}{T}
floor(2m_i-T-Tlfloorfrac{m_i}{T}
floor)}{2})f(T))
前面部分事实上是一个关于(T)的多项式，设为(g(T))，系数数组为(a)
对(lfloorfrac{m_i}{T}
floor)整除分块，我们每次要查询一个区间的值：(ans=sum_{T=l}^{r}G(T)f(T))
拿出(F)，(ans=sum_{i=0}^na_isum_{T=l}^rg(T),ans=sum_{i=0}^na_isum_{T=l}^rg(T)T^i)
后面是和询问无关的。
由于整除分块，多项式只有(nsqrt{mn})种，可以暴力乘积预处理
11.旧试题
(sum_{i=1}^Asum_{j=1}^Bsum_{k=1}^Cd(ijk))
(sum_{i=1}^Asum_{j=1}^Bsum_{k=1}^Csum_{x|A}sum_{y|B}sum_{z|C}[xperp y][xperp z][yperp z])
(sum_{x=1}^Asum_{y=1}^Bsum_{z=1}^C[xperp y][xperp z][yperp z]lfloorfrac{A}{x}
floorlfloorfrac{B}{y}
floorlfloorfrac{C}{z}
floor)
(sum_{x=1}^Asum_{y=1}^Bsum_{z=1}^Csum_{i|(x,y)}sum_{j|(x,z)}sum_{k|(y,z)}lfloorfrac{A}{x}
floorlfloorfrac{B}{y}
floorlfloorfrac{C}{z}
floor u(i)u(j)u(k))
(sum_{i=1}^{min(A,B)}sum_{j=1}^{min(A,C)}sum_{k=1}^{min(B,C)}u(i)u(j)u(k)(sum_{[x,y]|i}lfloorfrac{A}{i}
floor)(sum_{[x,z]|j}lfloorfrac{B}{y}
floor)(sum_{[y,z]|k}lfloorfrac{C}{z}
floor))
暴力枚举约数预处理形如((sum_{[x,y]|i}lfloorfrac{A}{i}
floor))的公式
这样子看上去时间复杂度还是(O(n^3))，但是事实上很多状态走不到
如果([x,y]>i)或者([x,z]>j)或者([y,z]>k)，则不合法
把(u==0)的节点去掉，然后把([x,y]leq n)的节点连边三元环计数
由于限制非常苛刻，打表后发现合法边不多。
12.蒜头的奖杯
前一道题理论上可以用这道题的做法解决，但是实际上过不去。
做法1："旧试题"反演，三个同时反演
(sum_{i=1}^Asum_{j=1}^Bsum_{k=1}^CA_iB_jC_kD_{gcd(i,j)}E_{gcd(i,k)}F_{gcd(j,k)})
考虑构造(gcd)的dirchlet卷积（这事实上也是莫反）
把(D,E,F)与(u)卷积，设为(D',E',F')
(sum_{i=1}^Asum_{j=1}^Bsum_{k=1}^CA_iB_jC_ksum_{x|gcd(i,j)}sum_{y|gcd(i,k)}sum_{z|gcd(j,k)}D'_{x}E'_{y}F'_{z})
提取(x,y,z)
(sum_{x=1}^Asum_{y=1}^Bsum_{z=1}^CD'_iE'_jF'_ksum_{[x,y]|i}sum_{[x,z]|j}sum_{[y,z]|k}A_iB_jC_k)
(sum_{[x,y]|i}sum_{[x,z]|j}sum_{[y,z]|k})的限制十分苛刻，要求([x,y]leq n)
所以也可以三元环计数
做法2：
考虑只反演两个
和前面一样用dirchlet卷积优化反演工作量，设(E,F)和(u)的卷积是(E',F')
(G(A)=sum_{ijleq n}A_j)
(sum_{i=1}^nsum_{j=1}^nsum_{k=1}^nA_iB_jC_kD_{gcd(i,j)}E_{gcd(i,k)}F_{gcd(j,k)})
(sum_{k=1}^nC_ksum_{i=1}^nsum_{j=1}^nA_iB_jD_{gcd(i,j)}sum_{a|(i,k)}sum_{b|(j,k)}E'_aF'_b)
拿出(sum_{a|(i,k)}sum_{b|(j,k)})
(sum_{frac{ab}{(a,b)}leq n}E'_aF'_bG(C)_{frac{ab}{(a,b)}}sum_{ialeq n}sum_{jbleq n}A_{ia}B_{jb}D_{gcd(ia,ib)})
枚举((a,b)=d)
(sum_{d}sum_{a}sum_{b,dableq n}[(a,b)=1]E'_{da}F'_{db}G(C)_{dab}sum_{iadleq n}sum_{jbdleq n}A_{iad}B_{jbd}D_{gcd(iad,jbd)})
令(H_i=A_{id},I_i=B_{id},J_i=C_{id})
要求(sum_{d}sum_{a}sum_{b,dableq n}[(a,b)=1]E'_{da}F'_{db}G(C)_{dab}sum_{x}sum_{y}H_{ax}I_{by}J_{gcd(ax,by)})
反演(J_{gcd(ax,by)})，设(J'=J*u)
([(a,b)=1]E'_{da}F'_{db}G(C)_{dab}sum_{a|X}H_{X}sum_{b|X}I_{b}sum_{b|z}J'_{z}[r|z])
考虑用dirchlet前缀和求出上式
设(t_a=J'_i[a|i])
用dirchlet后缀和求
设(t'_a=I_asum_{i|a}t_i)
用dirchlet前缀和求
(t''_a=H_asum_{a|i}t'_i)
用dirchlet后缀和求
枚举(d,a,b)，用(t'')的元素更新答案。
可以证明时间复杂度是(O(nsqrt{n}log_2log_2n))
13.一个人的数论
14.记忆
判定两个数乘起来是否是平方，根据定义，只需要关心每个素因子的个数(mod 2)的值是否等于(0)
把所有素因子的次数(mod 2)后，每一个素因子要么同时存在，要么不存在。
这事实上是"动态几何问题"的结论
先考虑(l=1)
定义(f(x))：把所有素因子的次数(mod 2)后的答案。
显然把所有(f(x))相同的数放在一起最优
枚举(f(x)=y)，则根据前面的分析，答案等于每组形如(x^2y)的数的数量(-1)。
转化后得到：区间内(f(x)=x)数
14.1 动态几何问题
14.2 完全平方数
显然二分。一个数含有平方因子就是它的(u)值(=0)
问题转化成询问一个前缀([1,x])有多少个整数不包含完全平方数，设为(x)。
考虑容斥
公式：所有数-为一个质因数平方的倍数+为2个质因数平方的倍数-....
这事实上是(u)的定义
于是得到公式：(f(x)=sum_{i^2< n}u(x)lfloorfrac{n}{i^2}
floor)
暴力计算即可。
15.FJWC lg
16.循环之美
有引理：(i,j)符合要求只有((i,j)=1)
知道这个引理后考虑反演
用整体思想，设(F(n,m,k)=sum_{i=1}^n sum_{j=1}^m [(i, j)=1][(j,k)=1])
对后面反演，(sum_{i=1}^n sum_{j=1}^m [(i, j)=1]sum_{d|j,d|k}u(d))
拿出(d)，(sum_{d|k}u(d)sum_{i=1}^nsum_{j=1}^{lfloorfrac{m}{d}
floor}[(i,jd)=1])
([(i,jd)=1]=[(i,j)=1][(i,d)=1])
这样子就能递归到子问题(sum_{d|k}u(d)sum_{i=1}^nF(lfloorfrac{m}{d}
floor,n,d))
当(k=1)时就不能递归了
但是问题转化成(sum_{i=1}^n sum_{j=1}^m [(i, j)=1])
根据前面的结论它等于(sum_{e=1}^nu(e)lfloorfrac{n}{e}
floorlfloorfrac{m}{e}
floor)
用整除分块，需要计算一段区间的(u)。可以杜教筛。
(F)要记忆化保证复杂度
17.公约数
考虑(i,j,k)的唯一分解，设某个质数为(p)，它包含(p^a,p^b,p^c)
把(a,b,c)从小到大排序。
(gcd(ij,ik,jk))的(p)幂次为(p^{a+b})
(gcd(i,j,k))的(p)幂次为(p^a)
(gcd(ij,ik,jk)*gcd(i,j,k))的(p)幂次为(p^{2a+b})
后面的式子通分后，含有p的幂次是(frac{x}{p^{2a+b}})
所以，我们要求(sum_{i=1}^nsum_{j=1}^msum_{k=1}^pgcd(i,j)+gcd(i,k)+gcd(j,k))
把这个拆成独立的3部分：((p*sum_{i=1}^nsum_{j=1}^mgcd(i,j))+(n*sum_{i=1}^psum_{j=1}^mgcd(i,j))+(m*sum_{i=1}^nsum_{j=1}^pgcd(i,j)))
然后就变成了于神之怒弱化版了。
18.太阳神
先容斥后枚举(gcd)，我们要求(sum_{d=1}^nsum_{i=1}^nsum_{j=1}^n[gcd(i,j)=d][ijleq nd]=sum_{d=1}^nsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}[gcd(i,j)=1][ijdleq n])
反演(gcd)，(sum_{d=1}^nsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}[ijdleq n]sum_{e|gcd(i,j)}u(e))
拿出(e)，(sum_{e=1}^nu(e)sum_{d=1}^{lfloorfrac{n}{e}
floor}sum_{i=1}^{lfloorfrac{n}{de}
floor}sum_{j=1}^{lfloorfrac{n}{de}
floor}[ijde^2leq n]=sum_{e=1}^nu(e)sum_{d=1}^{lfloorfrac{n}{e}
floor}sum_{i=1}^{lfloorfrac{n}{de}
floor}lfloorfrac{n}{ide^2}
floor)
发现(u(e))的上界是(sqrt{n})，这样子就不用杜教筛了。
同样考虑(i)的上界，它是(lfloorfrac{n}{de^2}
floor)。
设(f(n)=sum_{i=1}^nlfloorfrac{n}{i}
floor)，答案等于(sum_{e=1}^{sqrt{n}}u(e)sum_{d=1}^{lfloorfrac{n}{e}
floor}f(lfloorfrac{n}{de}
floor))
枚举(e)，对(lfloorfrac{n}{e}
floor)整除分块。
(f(i))只会用到(sqrt{n})个，可以整除分块
(f(n))事实上是(1...n)的所有数的约数个数和，可以积性筛前缀和预处理。
我居然连这都看不出来。。。。。
惨遭卡常，只有80
19.bzoj4659
(u)是积性函数，如果((i,j)
eq 1)，则(u(ij)=0)
(ans=sum_{i=1}^nsum_{j=1}^mu(i)u(j)[gcd(i,j)=1])
反演，(ans=sum_{i=1}^nsum_{j=1}^mu(i)u(j)sum_{d|gcd(i,j)}u(d))
发现不太能枚举(gcd(i,j))，考虑把(i)拿出来
(ans=sum_{i=1}^nu(i)sum_{d|i}u(d)sum_{j=1}^{frac{i}{k}} u(jk))
设(F_i=u_isum_{d|i}u(d)sum_{j=1}^{frac{i}{k}} u(jk))
(s_i=s_{i-1}+F_i)
如果(u_i
eq 0)才会对(s_i)产生贡献
后面可以暴力枚举(d)。
设(G(k,i)=sum_{j=1}^{frac{i}{k}} u(jk)[k|i])
显然只有(O(nlog_2n))种(G)合法。
(G(i+k,i)=sum_{j=1}^{frac{i}{k}+1} u(jk)[k|i]=G(k,i)+u(i+k))
于是可以在(O(nlog_2n))时间内递推(G)
G要滚动，否则会MLE
20.和与积
考虑((a,b)=d)，根据套路把(i,j/=d)，(d(i+j)|ijd^2,i+j|ijd)
此时((i,j)=1,(i+j,j)=(i,j+i)=1)
所以([i+j|ij]=[(i,j)=1,(i+j)=1])
(sum_{i=1}^nsum_{j=1}^{i-1}lfloorfrac{n}{i(i+j)}
floor[(i,j)=1])
显然反演，(sum_{i=1}^nsum_{j=1}^{i-1}lfloorfrac{n}{i(i+j)}
floorsum_{e|(i,j)}u(e)=sum_{e=1}^{sqrt{n}}u(e)sum_{i=1}^{lfloorfrac{sqrt{n}}{k}
floor}sum_{j=1}^{i-1}lfloorfrac{n}{ik(ik+jk)}
floor=sum_{e=1}^{sqrt{n}}u(e)sum_{i=1}^{lfloorfrac{sqrt{n}}{e}
floor}sum_{j=i+1}^{2*i-1}lfloorfrac{lfloorfrac{n}{ie^2}
floor}{j}
floor)
如果我们知道了(i,e)，则我们就知道了(lfloorfrac{n}{ie^2}
floor)，整除分块即可。
21.cf1097f
22.反回文串
23.简单的数论题
24.怎样跑得更快
用公式([i,j]=frac{ij}{gcd(i,j)})转化原式，(sum_{i=1}^n(i,j)^{c-d}i^dj^dx_jmod p=b_i)
令(e=c-d,x_i=i^dx_i,y_i=frac{b_i}{i^d},sum_{i=1}^n(i,j)^{e}x_jmod p=y_i)
前面提到了可以用dirchlet卷积化简计算，设(f=n^e*u)，(sum_{i=1}^nsum_{d|i,d|j}f(d)x_jmod p=y_i)
提取(d)，(sum_{d|i}f(d)sum_{d|j}x_jmod p=y_i)
令(g(d)=sum_{d|j}x_j)，原式变成(sum_{d|i}f(d)g(d)mod p=y_i)
令(h(i)=f(d)g(d))，则(sum_{d|i}h(d)mod p=y_i)
(h*I=y)，解这个方程可以dirchlet差分。
从(x)求(g)事实上是倍数型mobius反演，可以dirchlet差分，然后知道(g,h)后就能解出(f)和判定无解了
求(f)还要dirchlet差分。
由于数据范围较小，所以暴力即可。
总结：
在莫反内，使用这3个原则转化式子
构造杜教筛函数时，可以查"常见数论函数表"构造
反演时式子在满足规则时可以任意化简，如果一个式子化简不了，考虑向另一个方向化简。
如果化简不了了，则可以对式子拆成独立的部分，可以构造组合意义。
使用整体思维可能可以减少化简量，方法在于换元等。
在化简式子时，如果要优化一个部分，尽量把式子化简/移动成最简形式，否则后面计算时会很麻烦
在化简时，新的对于和式的限制要小心处理。
在化简时要注意函数值的特性，如果走不通了可以尝试利用函数值的特性
在计算时，只需要计算对答案有贡献的部分，就是不用计算0，这可能可以降低常数，或者减少上界而降低复杂度
在lg这道题时，在化简时很麻烦，所以可以提取出公因子考虑。
事实上，在化简时可以把式子拆成多个独立的部分，可能会让时间复杂度更优。
在你不知道一个算法的时间复杂度时，可以用它跑极限数据，这样子可以避免微积分估计。
莫反不一定要公式，还可以从组合意义（容斥）上理解。
如果一个式子内有较为复杂的限制，可以尝试忽略其中一个限制。
整体思维设出的数论函数可能可以递归求，时间复杂度可能是正确的。
在反演时，善用dirchlet卷积可以减少推导复杂度
如果遇到比较复杂无法反演的函数，可以尝试挖掘这个函数的性质。
在挖掘性质时，通常要把它拆解。