前言：
本题表中，凡是涉及\(n、m\)，都默认\(n \leq m\)。
如果你连莫比乌斯求\(\sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=1]\)都还不会,请去先入个门。 题目里面的各种套路还是很深的。 如果扎扎实实看完（并做完），一般的莫比乌斯反演肯定没问题了（当然不排除一些毒瘤题啦）。Part1
这些题目都非常水，莫比乌斯反演入门题，
主要是对莫比乌斯反演应用有一个基本概念。1.[HAOI2011]Problem b
()
题目：一组数据(\(a、d、c、d \leq 5×10^4\))求\[\sum_{i=a}^{b} \sum_{j=c}^d [gcd(i,j)=d]\] 题解：\[\sum_{i=1}^{n} \sum_{j=1}^m [gcd(i,j)=d] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i)\lfloor \frac{\lfloor \frac{n}{d} \rfloor}{i} \rfloor * \lfloor \frac{\lfloor \frac{m}{d} \rfloor}{i} \rfloor\] 数论分块，然后二维容斥即可。2.[NOI2010]能量采集
()
题目：一组数据(\(n、m \leq 10^5\))，求\[2*\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) - n*m\] 题解：\[\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) =\sum_{d=1}^nd \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] \] 枚举\(d\)，然后用第1题的方法搞即可。3.Gcd
()
题目：一组数据,给定整数\(N(N\leq10^7)\)，求\(1 \leq x,y \leq N\)且\(Gcd(x,y)\)为素数的组数 题解：\[\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) =\sum_{d=2}^{d \leq n} d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] \] 枚举素数\(d\)，然后用第1题的方法搞即可。4.[中山市选2011]完全平方数
()
题目：\(50\)组数据,给出\(k\)，求第\(k\)个不是完全平方数的倍数的数是多少。\(k \leq 10^9\) 题解： 先二分一个\(n\),然后检查\(n\)下面有多少个非完全平方数。计算方法为： 设\(f(i)\)表示只为\(i^2\)倍数，并且不是其它平方数倍数的数的个数。 那么令\(F(i) = f(i)+f(2i)+....+f(ki)\)，即为\((ri)^2\)倍数的数的个数。 那么\(F(i) = \sum_{i|d} f(d)\)。显然\(F(n) = \lfloor \frac{n}{i^2} \rfloor\) 反演一下：\[f(1) = \sum_{i=1}^{\lceil \sqrt{n} \rceil } \lfloor \frac{n}{i^2} \rfloor\] 直接数论分块即可得到一个数\(n\)的排名\(f(1)\)。Part2
这一部分的题就相当有难度了（跨度这么大我也很无奈啊）
5.[BZOJ2154]Crash的数字表格
()
题目：一组数据，输入\(n\)、\(m\)，(\(n、m \leq 10^7\))，求：\[\sum_{i=1}^n \sum_{j=1}^m lcm(i,j) \quad mod \quad 20101009\] 题解：\[Ans = \sum_{i=1}^n \sum_{j=1}^m lcm(i,j) = \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{gcd(i,j)} = \sum_{d=1}^n \frac{f(n,m,d)}{d}\] 其中\[f(n,m,d) = \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d]*ij = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{i=1}^{\lfloor \frac{m}{d} \rfloor} ij*[gcd(i,j)=1]*d^2\] 带回原式中：\[Ans = \sum_{d=1}^n d*f({\lfloor \frac{n}{d} \rfloor},{\lfloor \frac{m}{d} \rfloor},1) \] 考虑一下函数 \(f\) 的求法：\[f({n},{m},d) = \sum_{i=1}^{n } \sum_{i=1}^{m } ij*[gcd(i,j)=d] = f(d)\] 令\[F(d) = \sum_{i=1}^{ {n}} \sum_{i=1}^{ {m}} ij*[d|gcd(i,j)] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{i=1}^{\lfloor \frac{m}{d} \rfloor} ij= \sum_{n|d} f(d)\] 反演一下：\[f(i) = \sum_{i|d}\mu(\frac{d}{i})F(d) , f(1) = \sum_{d=1}^n\mu(d)F(d) = \sum_{d=1}^n\mu(d) \sum_{i=1}^{ {\lfloor \frac{n}{d} \rfloor}} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij\] 显然\(\sum_{i=1}^{ {n}} \sum_{j=1}^{ {m}} ij = \sum_{i=1}^{ {n}} i *\sum_{j=1}^{ {m}} j = \frac{n*(n+1)}{2} * \frac{m*(m+1)}{2}\) 总结一下，得到了两个式子：\[Ans = \sum_{d=1}^n d*f({\lfloor \frac{n}{d} \rfloor},{\lfloor \frac{m}{d} \rfloor},1) \]\[f({n},{m},1) = \sum_{d=1}^n\mu(d) \frac{\lfloor \frac{n}{d} \rfloor*(\lfloor \frac{n}{d} \rfloor+1)}{2} * \frac{\lfloor \frac{m}{d} \rfloor*(\lfloor \frac{m}{d} \rfloor+1)}{2}\] 两个式子都可以数论分块，所以复杂度为:\(O(\sqrt{n})*O(\sqrt{n})=O({n})\)6.[SDOI2015]约数个数和
()
题目：\(5×10^4\)组数据，输入\(n,m\)\((n,m \leq 5×10^4)\),\(d(x)\)表示\(x\)的约数个数,求：\[\sum_{i=1}^n \sum_{j=1}^m d(ij)\] 题解： 首先,有定理：\[d(ij) = \sum_{t1|i} \sum_{t2|j} [gcd(t1,t2)=1]\] 证明: 对于一个约数\(d\)，它必定由\(i\)的一个约数与\(j\)的一个约数的乘积。 为了防止算重，我们规定\(gcd(t1,t2)=1\)才计算。 因为每一个数一定可以被表示为两个互质的数的乘积,所以这样计算是正确的。 同样这样的\(t1\)和\(t2\)一定存在于\(i\)和\(j\)的约数中，因为唯一分解定理 所以把原式化为：\[Ans =\sum_{i=1}^n \sum_{j=1}^m \sum_{t1|i} \sum_{t2|j} [gcd(t1,t2)=1]\] 四个\(\sum\)很不好看（也不好搞）,单独考虑二元组(i,j)的贡献：\[Ans = \sum_{u=1}^n \sum_{v=1}^m [gcd(u,v)=1] \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{v} \rfloor\] 令\[f(d) = \sum_{u=1}^n \sum_{v=1}^m [gcd(u,v)=d] \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{v} \rfloor\] 同理令\[F(d) = \sum_{u=1}^n \sum_{v=1}^m [d|gcd(u,v)] \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{v} \rfloor = \sum_{u=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{u=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{ud} \rfloor \lfloor \frac{m}{vd} \rfloor\] 所以\[F(d) = \sum_{u=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{u=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{ud} \rfloor \lfloor \frac{m}{vd} \rfloor = \sum_{u=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{ud} \rfloor *\sum_{u=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{vd} \rfloor = sum(\lfloor \frac{n}{d} \rfloor)*sum(\lfloor \frac{m}{d} \rfloor)\] 其中\(sum(x)=\sum_{i=1}^{x} \lfloor \frac{x}{i} \rfloor\)表示\(1\)到\(x\)的约数个数和，不懂为什么见 又因为\[F(i) = \sum_{i|d}f(d)\] 莫比乌斯反演一波:\[f(1) = \sum_{i=1}^n \mu(i)F(i) = \sum_{i=1}^n \mu(i) sum(\lfloor \frac{n}{i} \rfloor)*sum(\lfloor \frac{m}{i} \rfloor) = Ans\] 其中\[sum(x)=\sum_{i=1}^{x} \lfloor \frac{x}{i} \rfloor\] 显然先 数论分块 预处理\(sum(x)\),然后每次询问也数论分块求解\(f(1)\)即可。 总的复杂度为：预处理\(O(n \sqrt{n})\) , 询问 \(O(T \sqrt{n})\)。7. [SDOI2017]数字表格
()
题目：\(f(i)\)为斐波那契数列第\(i\)项，定义\(f(0)=0,f(1)=1\)。 总共输入\(10^3\)组数据，每次输入\(n,m\)\((n,m \leq 10^6)\)，时限\(5 sec\)，求：\[\prod_{i=1}^n \prod_{j=1}^m f(gcd(i,j))\] 题解： 肯定先要提出\(gcd(i,j)\)：\[Ans = \prod_{i=1}^n \prod_{j=1}^m f(gcd(i,j)) = \prod_{d=1}^n f(d)^{\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1]}\] 上面那一坨提出来看(直接跳步骤了)\[\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) {\lfloor \frac{n}{id} \rfloor} {\lfloor \frac{m}{id} \rfloor} = r(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)\]\[Ans = \prod_{d=1}^n f(d)^{r(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\] 显然\(Ans\)与\(r(n,m)\)的求解都可以数论分块，此时复杂度为\(O(n)\)可以跑过单组数据。 但是我们有多组数据，考虑如何优化。 看到\(id\),是不是感觉很套路？令\(T = id\) , 那么我们把\(T\)给提出来：\[\prod_{d=1}^n f(d)^{\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) {\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}} = \prod_{T=1}^n(\prod_{d|T} f(d)^{\mu(\frac{T}{d})})^{ {\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}}\] 令\[R(T) = \prod_{d|T} f(d)^{\mu(\frac{T}{d})}\] 这显然是可以\(O(n log^2(n))\)直接暴力算出来的(因为是枚举因数啊)。 那么\[Ans = \prod_{T=1}^n(\prod_{d|T} f(d)^{\mu(\frac{T}{d})})^{ {\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}} = \prod_{T=1}^nR(T)^{ {\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}}\] 显然\(R(T)\)是可以记乘法前缀和的，所以每次询问时数论分块搞一波即可。 总的复杂度： 预处理\(O(n log^2(n))\) , 询问\(O(T \sqrt{n}log(n))\)。Part3
其实比较关键的题目就是\(Part2\)里的三题了，剩下的这些题当做补充练习。
8. GCD-2(YY的GCD)
()
题目：\(10^5\)组数据,给定整数\(N,M(\leq10^7)\)，求\(1 \leq x\leq N\) , \(1 \leq y\leq M\) ,且\(Gcd(x,y)\)为素数的组数。 题解： 其实就是第三题《\(GCD\)》的升级版。 前面的步骤直接跳过：\[Ans = \sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) \lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{id} \rfloor\] 老套路，令\(T = id\)，提出\(T\)：\[\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) \lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{id} \rfloor = \sum_{T=1}^n \sum_{d|T} \mu(\frac{T}{d}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor = \sum_{T=1}^n\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d|T} \mu(\frac{T}{d})\] 然后只要考虑这个玩意怎么搞即可：\[R(T) = \sum_{d|T} \mu(\frac{T}{d})\] 额...还记得在讲素数时说的那个结论吗？ 结论回顾： 质数的密度大约是\(\frac{1}{10}\)! 所以\(O(10^7k) ------> O(10^6k)?\) 嗯，好像是这样，所以暴力埃式筛即可。9. [UVa11426]最大公约数之和——极限版II
()
题目：\(10^2\)组数据,给定整数\(n,m(\leq10^7)\),求：\[\sum_{i=1}^{n-1} \sum_{j=i+1}^n gcd(i,j)\] 题解： 其实就是第二题《能量采集》的升级版。 考虑二元组\((i,j)\)的构成形式，一共三种：\(i<j\) 、\(i=j\)、\(i>j\)。 所以只要求\(\sum_{i=1}^n \sum_{j=1}^n gcd(i,j) = Ans'\)，那么显然：\[Ans = \frac{(Ans' - \sum_{i=1}^n i)}{2}\] 下面求\(Ans'\)，前面的步骤直接跳过：\[Ans' = \sum_{d=1}^n d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) {\lfloor \frac{n}{id} \rfloor }^2\] 还是老套路（套路就是这么神奇），令\(T = id\)，提出\(T\)：\[Ans' = \sum_{T=1}^n \sum_{d|T} \mu(\frac{T}{d}) {\lfloor \frac{n}{T} \rfloor }^2 d = \sum_{T=1}^n {\lfloor \frac{n}{T} \rfloor }^2\sum_{d|T} \mu(\frac{T}{d}) d \] 那么显然下面这个东东：\[R(x) = \sum_{d|T} \mu(\frac{T}{d})*d\] 是一个狄利克雷卷积 ， 直接积性函数线性筛即可。10.HDU4746: \(Mophues\)
()
名字莫名诡异.... 题目：\(5*10^3\)组数据 ， 每次给定一个\(n,m,p\)(\(<=5*10^5\))，求：\[\sum_{i=1}^n \sum_{j=1}^m [h(gcd(i,j)) \leq p]\] 其中其中\(h(x)\)表示一个数质因数分解后质数的个数。例如：\(12=2×2*3\),那么\(h(12)=3\)。 题解： 非常有意思的一题。 首先大力化式子（与前面所有题目方法类似）：\[Ans = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d|T} [h(d) \leq p] \mu(\frac{T}{d}) = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor R(p,T)\] 考虑如何求\(R(p,T)\)：\[R(p,T) = \sum_{d|T} [h(d) \leq p] \mu(\frac{T}{d})\] 发现在\([1,n]\)中，\(h(i) \leq 18\) , （\(2^{18} = 262144\) , \(2^{19} = 524288\)） 所以就非常神奇了 ， 当\(18 < p\)时，直接输出\(n*m\)即可。 所以只要处理\(0 \leq p \leq 18\)的前缀和即可。 这个还是比较简单的吧，分\(3.5\)步走： （0）显然\(h(i)\)在求\(\mu(i)\)时可以顺便求出来。 （1）埃氏筛处理\(E(p,x) = \sum_{d|T} [h(d) = p] \mu(\frac{T}{d})\) （2）统计一下\(S(p,x) = \sum_{i=1}^p E(i,x)\) （3）统计一下\(R(p,x) = \sum_{i=1}^x S(p,i)\) 然后每次询问时直接调用\(R(p,x)\)，接着数论分块即可。11.[ZOJ3435]Ideal Puzzle Bobble
()
题目：求：\[\sum_{i=1}^L \sum_{j=1}^W \sum_{k=1}^H[gcd(i,j,k)==1]\] 题解：12.来历不明的火题：
题目：一组数据,给定\(n,k\)(\(n \leq 10^7\) , \(k \leq 10^5\)) , 求：
\[\sum_{i=1}^n \sum_{j=1}^m i^kj^k*gcd(i,j)\] 题解： 首先先打一个预防针：\(q(i)=i^k\)请线性筛好不然肯定会超时。 然后先化式子：\[Ans = \sum_{d=1}^n d^{2k+1} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i,j)=1]i^kj^k = \sum_{d=1}^n d^{2k+1} R(\lfloor \frac{n}{d} \rfloor)\] 然后求解\(R(x)\)：\[f(d) = \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i,j)=d]i^kj^k \] 所以构造倍数形式莫比乌斯：\[F(d) = \sum_{j=1}^{n}[d|gcd(i,j)]i^kj^k = \sum_{d=1}^{n}d^{2k}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}i^kj^k\] 上面这步是关键(提出\(d\))，然后继续化：\[F(d) = \sum_{d=1}^{n}d^{2k}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}i^k *\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}j^k = \sum_{d=1}^n d^{2k} *[sum(\frac{n}{d})]^2 \ ;\] 其中\(sum(d)\)为乘法前缀和，预处理一下即可。 接着就可以莫比乌斯反演了：\[R(n) = f(1) = \sum_{d=1}^n \mu(d) F(d) = \sum_{d=1}^n \mu(d) d^{2k} sum(\lfloor \frac{n}{d} \rfloor) \ ;\]\[Ans = \sum_{d=1}^n d^{2k+1} R(\lfloor \frac{n}{d} \rfloor)\] 注意一下$x^{2k}=(x^k)^2 ; x^{2k+1} = x^{2k}*x $ , 不能用快速幂。 显然两边都可以数论分块，\(O(n)\)计算即可 ， 注意常数问题。Part INF
这里总结一下套路：
（1）遇见\(id\)形式，换元提出\(T=id\)：\[Sample=\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\mu({i}) \lfloor \frac{n}{id} \rfloor = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \sum_{d|T}\mu(\frac{T}{d}) \] 那么后面那一坨就很有可能可以线性筛、分块(