听起来很难，但其实跟着lyy仔细推一推感觉也还好的。。
莫比乌斯函数：
令n=∏i=1kpiαin=\prod_{i=1}^{k}{p_i^{\alpha_i}}n=∏i=1k piαi ，则：
μ(n)={1n=1(−1)kn=p1p2⋯pk（pi 为互异素数）0其他情况（n 有平方因子）\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n = p_1 p_2 \cdots p_k \text{（}p_i\text{ 为互异素数）} \\ 0 & \text{其他情况（}n\text{ 有平方因子）} \end{cases} μ(n)=⎩⎨⎧ 1(−1)k0 n=1n=p1 p2 ⋯pk （pi 为互异素数）其他情况（n 有平方因子）
狄利克雷卷积
定义两个函数fff和ggg的卷积为(f∗g)(n)(f*g)(n)(f∗g)(n)，则：
(f∗g)(n)=∑d∣nf(d)×g(nd)(f*g)(n)=\sum_{d|n}{f(d)\times g(\frac{n}{d})} (f∗g)(n)=d∣n∑ f(d)×g(dn )
其具有的性质有：
1.交换律：f∗g=g∗ff*g=g*ff∗g=g∗f
2.结合律：(f∗g)∗h=f∗(g∗h)(f*g)*h=f*(g*h)(f∗g)∗h=f∗(g∗h)
3.分配律：f∗(g+h)=f∗g+f∗hf*(g+h)=f*g+f*hf∗(g+h)=f∗g+f∗h
一些函数
1.ϵ(n)\epsilon(n)ϵ(n)，又称单位函数。
ϵ(n)=[n=1]\epsilon(n)=[n=1] ϵ(n)=[n=1]
2.I(n)I(n)I(n)，又称常数函数。
I(n)=1I(n)=1 I(n)=1
3.Idk(n)Id_k(n)Idk (n)
Idk=nk，特别的Id1=IdId_k=n^k，特别的Id_1=Id Idk =nk，特别的Id1 =Id
一些卷积恒等式
1.μ∗I=ϵ\mu *I=\epsilonμ∗I=ϵ，即
∑d∣nμ(d)=[n=1]\sum_{d|n} \mu(d) = [n=1] d∣n∑ μ(d)=[n=1]
证明：
令n=∏i=1kpiαin=\prod_{i=1}^{k}{p_i^{\alpha_i}}n=∏i=1k piαi ，n′=∏i=1kpin'=\prod_{i=1}^{k}{p_i}n′=∏i=1k pi ，显然∑d∣nμ(d)=∑d′∣nμ(d′)\sum_{d|n}{\mu(d)}=\sum_{d'|n}{\mu(d')}∑d∣n μ(d)=∑d′∣n μ(d′)。
接着考虑贡献，这就是一个组合数的问题，每个质因子选或不选：
∑d∣nμ(d)=∑i=1k(ki)×(−1)k=(1−1)k=0\sum_{d|n}{\mu(d)}=\sum_{i=1}^{k}{\binom{k}{i}}\times (-1)^k=(1-1)^k=0 d∣n∑ μ(d)=i=1∑k (ik )×(−1)k=(1−1)k=0
而且显然当n=1n=1n=1时总和才会为111
2.ϕ∗I=Id\phi * I=Idϕ∗I=Id，证明：
按照定义带入：∑d∣nϕ(d)=n\sum_{d|n}{\phi}(d)=n∑d∣n ϕ(d)=n看起来证明很复杂？其实我也不会，好吧，感觉思路听巧妙的。。
将所有分数：1n,2n...\frac{1}{n},\frac{2}{n}...n1 ,n2 ...化为最简分数，对于每个d∣nd|nd∣n做分母，恰好有一个1≤k≤d1\le k \le d1≤k≤d使得(k,d)=1(k,d)=1(k,d)=1，所以有ϕ(d)\phi(d)ϕ(d)个，得证。
3.Id∗μ=ϕId* \mu=\phiId∗μ=ϕ，证明：
由μ∗I=ϵ\mu*I=\epsilonμ∗I=ϵ，将式子ϕ∗I=Id\phi*I=Idϕ∗I=Id同时卷积上μ\muμ，则：
ϕ∗I∗μ=Id∗μ ⟹ ϕ=Id∗μ\phi * I * \mu=Id * \mu \implies \phi=Id*\mu ϕ∗I∗μ=Id∗μ⟹ϕ=Id∗μ
得证。
当然还有更多，大部分用的少，有用到的在补吧。。
莫比乌斯反演
形式1：若g(n)=∑d∣nf(d)g(n)=\sum_{d|n}{f(d)}g(n)=∑d∣n f(d)，即g=f∗1g=f*1g=f∗1，则有：
f(n)=∑d∣nμ(d)×g(nd)f(n)=\sum_{d|n}{\mu(d)\times g(\frac{n}{d})} f(n)=d∣n∑ μ(d)×g(dn )
证明用卷积很好证，这就不给了。
形式2：若g(n)=∑n∣df(d)g(n)=\sum_{n|d}{f(d)}g(n)=∑n∣d f(d)，则有：
f(n)=∑n∣dμ(dn)×g(d)f(n)=\sum_{n|d}{\mu(\frac{d}{n})\times g(d)} f(n)=n∣d∑ μ(nd )×g(d)
这个证明挺难的，反正我不会，谁会踢我一下。。
线性筛求Φ\PHIΦ和Μ\MUΜ
按照定义来就行，直接贴代码吧。
核心应用
考虑基础问题，用这个做一个引入：
∑i=1n∑j=1n[(i,j)=1]=?\sum_{i=1}^{n}\sum_{j=1}^{n}{[(i,j)=1]}=? i=1∑n j=1∑n [(i,j)=1]=?
我们可以将一个正方形分成两个三角形，每个三角形中一个数iii，∀j≤i\forall j\le i∀j≤i与iii互质的数恰好是有ϕ(i)\phi(i)ϕ(i)个，当然ϕ(1)\phi(1)ϕ(1)单独考虑。
所以：
∑i=1n∑j=1n[(i,j)=1]=1+2×∑i=2nϕ(i)=2×∑i=1nϕ(i)−1\sum_{i=1}^{n}\sum_{j=1}^{n}{[(i,j)=1]}=1+2\times \sum_{i=2}^{n}{\phi(i)}=2\times \sum_{i=1}^{n}{\phi(i)}-1 i=1∑n j=1∑n [(i,j)=1]=1+2×i=2∑n ϕ(i)=2×i=1∑n ϕ(i)−1
当然这道题中你还要考虑(0,1)(1,0)(0,1)(1,0)(0,1)(1,0)的两个情况。
那当n≠mn \not= mn=m：
∑i=1n∑j=1m[(i,j)=1]=?\sum_{i=1}^{n}\sum_{j=1}^{m}{[(i,j)=1]}=? i=1∑n j=1∑m [(i,j)=1]=?
显然刚刚的做法不可做了，那怎么办？
我们钦定n≤mn\le mn≤m
考虑对(i,j)=1(i,j)=1(i,j)=1做转化：
[(i,j)=1] ⟹ ϵ((i,j)=1) ⟹ ∑d∣(i,j)μ(d) ⟹ ∑d∣i,d∣jμ(d)[(i,j)=1] \implies \epsilon((i,j)=1) \implies \sum_{d|(i,j)}\mu(d) \implies \sum_{d|i,d|j}{\mu(d)} [(i,j)=1]⟹ϵ((i,j)=1)⟹d∣(i,j)∑ μ(d)⟹d∣i,d∣j∑ μ(d)
所以：
∑i=1n∑j=1m[(i,j)=1]=∑i=1n∑j=1m∑d∣i,d∣jμ(d)\sum_{i=1}^{n}\sum_{j=1}^{m}{[(i,j)=1]}=\sum_{i=1}^{n}\sum_{j=1}^{m} \sum_{d|i,d|j}{\mu(d)} i=1∑n j=1∑m [(i,j)=1]=i=1∑n j=1∑m d∣i,d∣j∑ μ(d)
显然可以交换求和顺序：
⟹ ∑d=1n∑i=1n[d∣i]∑j=1m[d∣j]×μ(d) ⟹ ∑d=1nμ(d)×⌊nd⌋×⌊md⌋\implies \sum_{d=1}^{n} \sum_{i=1}^{n}[d|i]\sum_{j=1}^{m}{[d|j]}{\times \mu(d)} \implies \sum_{d=1}^{n} {\mu(d) \times \lfloor \frac{n}{d} \rfloor \times \lfloor \frac{m}{d} \rfloor} ⟹d=1∑n i=1∑n [d∣i]j=1∑m [d∣j]×μ(d)⟹d=1∑n μ(d)×⌊dn ⌋×⌊dm ⌋
显然后面的那个东西可以用整除分块做，这样时间复杂度能做到N\sqrt{N}N 级别。
拓展1：给定kkk，∑i=1n∑j=1m[(i,j)=k]=?\sum_{i=1}^{n}\sum_{j=1}^{m}{[(i,j)=k]}=?∑i=1n ∑j=1m [(i,j)=k]=?
显然将kkk提出去，nnn和mmm间有⌊nk⌋\lfloor \frac{n}{k} \rfloor⌊kn ⌋和⌊mk⌋\lfloor \frac{m}{k} \rfloor⌊km ⌋个kkk的倍数（就跟上面的转化一样），变为：
∑i=1⌊nk⌋∑j=1⌊mk⌋[(i,j)=1]\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}{[(i,j)=1]} i=1∑⌊kn ⌋ j=1∑⌊km ⌋ [(i,j)=1]
套板子即可。
拓展2：求∑i=1n∑j=1mgcd(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m} gcd(i,j)∑i=1n ∑j=1m gcd(i,j)。
根据Id=ϕ∗IId=\phi * IId=ϕ∗I得，gcd(i,j)=∑d∣i,d∣jϕ(d)gcd(i,j)=\sum_{d|i,d|j}{\phi(d)}gcd(i,j)=∑d∣i,d∣j ϕ(d)即可做完，可以自己推一下。
P2522 [HAOI2011] PROBLEM B
显然一个容斥原理，画个图你们就明白了：
当然上下界自己想清楚。。。
GCD
一道非常幽默的题，题解区都是欧拉函数的做法，但显然这也是一个莫比乌斯反演的板子，枚举[1,107][1,10^7][1,107]质数，跑一个板子即可。
但你们可能想问复杂度不是O(nlognn)O(\frac{n}{\log n}\sqrt{n})O(lognn n )吗，不是过不了吗？
但是你们想一下，每次枚举质数，单次复杂度是O(np)O(\sqrt{\frac{n}{p}})O(pn )的，算一下：
总复杂度：
∑p≤nnp=n∑p≤n1p\sum_{p \le n} \sqrt{\frac{n}{p}} = \sqrt{n} \sum_{p \le n} \frac{1}{\sqrt{p}} p≤n∑ pn =n p≤n∑ p 1
根据素数定理和积分估计：
∑p≤n1p≈∫2n1t⋅1lnt dt≈2nlnn\sum_{p \le n} \frac{1}{\sqrt{p}} \approx \int_{2}^{n} \frac{1}{\sqrt{t}} \cdot \frac{1}{\ln t} \, dt \approx \frac{2\sqrt{n}}{\ln n} p≤n∑ p 1 ≈∫2n t 1 ⋅lnt1 dt≈lnn2n
所以总复杂度：
n⋅2nlnn=2nlnn≈2×107ln(107)≈2×10716.1≈1.24×106\sqrt{n} \cdot \frac{2\sqrt{n}}{\ln n} = \frac{2n}{\ln n} \approx \frac{2 \times 10^7}{\ln(10^7)} \approx \frac{2 \times 10^7}{16.1} \approx 1.24 \times 10^6 n ⋅lnn2n =lnn2n ≈ln(107)2×107 ≈16.12×107 ≈1.24×106
显然稳过，代码不放了，板子来的。
CRASH数字表格
非常爽的推柿子，我还是太蒻了，推一半卡住了，还要别人提醒我一下。
求∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}{lcm(i,j)}∑i=1n ∑j=1m lcm(i,j)。
令n≤mn\le mn≤m
∑i=1n∑j=1mlcm(i,j)=∑i=1n∑j=1mi×jgcd(i,j)=∑i=1n∑j=1mi×j∑d=1n[gcd(i,j)=d]d=∑d=1n∑i=1n∑j=1mi×j×[gcd(i,j)=d]d=∑d=1n∑x=1⌊nd⌋∑y=1⌊md⌋x×y×d2×[gcd(x,y)=1]d=∑d=1n∑x=1⌊nd⌋∑y=1⌊md⌋x×y×d×[gcd(x,y)=1]=∑d=1n∑x=1⌊nd⌋∑y=1⌊md⌋x×y×d∑k∣x,k∣yμ(k)=∑d=1n∑x=1⌊nd⌋∑y=1⌊md⌋x×y×d∑k=1⌊nd⌋μ(k)[k∣x][k∣y]=∑d=1nd∑k=1⌊nd⌋μ(k)∑i×k=1⌊nd⌋i×k∑j×k=1⌊md⌋j×k=∑d=1nd∑k=1⌊nd⌋μ(k)∑i=1⌊nd×k⌋i∑j=1⌊md×k⌋j\begin{aligned}
\sum_{i=1}^{n}\sum_{j=1}^{m}{lcm(i,j)}&=\sum_{i=1}^{n}\sum_{j=1}^{m}{\frac{i\times j}{gcd(i,j)}}\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j \sum_{d=1}^{n}{\frac{[gcd(i,j)=d]}{d}}\\ &=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j\times \frac{[gcd(i,j)=d]}{d}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor
\frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d^2\times \frac{[gcd(x,y)=1]}{d}}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d\times [gcd(x,y)=1]}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor
\frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d\sum_{k|x,k|y}{\mu(k)}}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}{\mu(k)[k|x][k|y]}}\\
&=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i\times k=1}^{\lfloor \frac{n}{d} \rfloor}i \times k\sum_{j\times k=1}^{\lfloor \frac{m}{d} \rfloor} j\times k\\ &=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d\times k}
\rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d\times k} \rfloor} j\\ \end{aligned} i=1∑n j=1∑m lcm(i,j) =i=1∑n j=1∑m gcd(i,j)i×j =i=1∑n j=1∑m i×jd=1∑n d[gcd(i,j)=d] =d=1∑n i=1∑n j=1∑m i×j×d[gcd(i,j)=d] =d=1∑n x=1∑⌊dn ⌋ y=1∑⌊dm ⌋ x×y×d2×d[gcd(x,y)=1] =d=1∑n x=1∑⌊dn ⌋ y=1∑⌊dm ⌋ x×y×d×[gcd(x,y)=1]=d=1∑n
x=1∑⌊dn ⌋ y=1∑⌊dm ⌋ x×y×dk∣x,k∣y∑ μ(k)=d=1∑n x=1∑⌊dn ⌋ y=1∑⌊dm ⌋ x×y×dk=1∑⌊dn ⌋ μ(k)[k∣x][k∣y]=d=1∑n dk=1∑⌊dn ⌋ μ(k)i×k=1∑⌊dn ⌋ i×kj×k=1∑⌊dm ⌋ j×k=d=1∑n dk=1∑⌊dn ⌋ μ(k)i=1∑⌊d×kn ⌋ ij=1∑⌊d×km ⌋ j
令f1(n,m)=∑i=1ni∑j=1mjf1(n,m)=\sum_{i=1}^{n}i\sum_{j=1}^{m}jf1(n,m)=∑i=1n i∑j=1m j，显然可以O(1)O(1)O(1)算。
再令f2(n,m)=∑i=1nμ(i)×f1(⌊ni⌋,⌊mi⌋)f2(n,m)=\sum_{i=1}^{n}\mu(i)\times f1(\lfloor \frac{n}{i} \rfloor,\lfloor \frac{m}{i} \rfloor)f2(n,m)=∑i=1n μ(i)×f1(⌊in ⌋,⌊im ⌋)，显然对f1(⌊ni⌋,⌊mi⌋)f1(\lfloor \frac{n}{i} \rfloor,\lfloor \frac{m}{i} \rfloor)f1(⌊in ⌋,⌊im ⌋)这个东西当每块定值，进行整除分块。
最后再对整体来一个整除分块即可。
约数和
想做出这道题，有一个非常重要的结论，ddd为积性函数。
所以对于d(i×j)d(i\times j)d(i×j)，枚举iii和jjj的因子，若gcd(x,y)=1gcd(x,y)=1gcd(x,y)=1则其必然为i×ji\times ji×j 的一个答案贡献，即：
d(i×j)=∑x∣i∑y∣j[gcd(x,y)=1]d(i\times j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] d(i×j)=x∣i∑ y∣j∑ [gcd(x,y)=1]
既然这样很显然就可以开始推柿子了（建议自己推一下）
∑i=1n∑j=1md(i×j)=∑i=1n∑j=1m∑x∣i∑y∣j[gcd(x,y)=1]=∑i=1n∑j=1m∑x=1n∑y=1m[x∣i][y∣j][gcd(x,y)=1]=∑x=1n∑y=1m∑i=1⌊nx⌋∑j=1⌊my⌋[gcd(x,y)=1]=∑x=1n∑y=1m∑i=1⌊nx⌋∑j=1⌊my⌋∑d∣x,d∣yμ(d)=∑d=1n∑x=1⌊nd⌋∑y=1⌊md⌋∑i=1⌊nd×x⌋∑j=1⌊md×y⌋μ(d)=∑d=1nμ(d)∑x=1⌊nd⌋⌊nd×x⌋∑y=1⌊md⌋⌊md×y⌋\begin{aligned}
\sum_{i=1}^{n}\sum_{j=1}^{m}d(i\times j)&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x=1}^{n}\sum_{y=1}^{m}[x|i][y|j][gcd(x,y)=1]\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{\lfloor \frac{n}{x} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{y} \rfloor}
[gcd(x,y)=1]\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{\lfloor \frac{n}{x} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{y} \rfloor}\sum_{d|x,d|y}{\mu(d)}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} \sum_{i=1}^{\lfloor \frac{n}{d \times x}
\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d \times y} \rfloor} \mu(d)\\ &=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{d\times x} \rfloor \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{d\times y} \rfloor \end{aligned} i=1∑n j=1∑m d(i×j) =i=1∑n j=1∑m x∣i∑ y∣j∑
[gcd(x,y)=1]=i=1∑n j=1∑m x=1∑n y=1∑m [x∣i][y∣j][gcd(x,y)=1]=x=1∑n y=1∑m i=1∑⌊xn ⌋ j=1∑⌊ym ⌋ [gcd(x,y)=1]=x=1∑n y=1∑m i=1∑⌊xn ⌋ j=1∑⌊ym ⌋ d∣x,d∣y∑ μ(d)=d=1∑n x=1∑⌊dn ⌋ y=1∑⌊dm ⌋ i=1∑⌊d×xn ⌋ j=1∑⌊d×ym ⌋ μ(d)=d=1∑n μ(d)x=1∑⌊dn ⌋ ⌊d×xn ⌋y=1∑⌊dm ⌋ ⌊d×ym ⌋
令f(i)=∑j=1i⌊ij⌋f(i)=\sum_{j=1}^{i}\lfloor \frac{i}{j} \rfloorf(i)=∑j=1i ⌊ji ⌋，显然这个东西可以O(NN)O(N\sqrt{N})O(NN )预处理。
然后还是对后面的东西进行整除分块即可。
