这文章好水啊。。。
公式：
原始版：
推论式：
简单应用：
设(f(x)=displaystylesum_{i=1}^{n}sum_{j=1}^m[gcd(i,j)=x])，(g(x)=displaystylesum_{x|d}f(d)).
根据莫比乌斯反演可得：(f(x)=displaystylesum_{x|d}mu(frac{d}{x})g(d)).
(g(x)=displaystylesum_{i=1}^nsum_{j=1}^m[x|gcd(i,j)])
(=displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}sum_{j=1}^{lfloorfrac{m}{x} floor}[1|gcd(i,j)])
(={lfloorfrac{n}{x} floor} imes {lfloorfrac{m}{x} floor})
所以(f(x)=displaystylesum_{i=1}^{lfloorfrac{min(n,m)}{x} floor}mu(i)g(icdot x)=displaystylesum_{i=1}^{lfloorfrac{min(n,m)}{x} floor}mu(i) imes {lfloorfrac{n}{ix} floor} imes {lfloorfrac{m}{ix} floor})
引理1：({lfloorfrac{n}{ab} floor}={lfloorfrac{lfloorfrac{n}{a} floor}{b} floor}).
引理2：设集合(S={{lfloorfrac{n}{x} floor}|1leq xleq n,xin mathbb{N}})，则(|S|=O(sqrt{n})).
证明都略了
(f(x)=displaystylesum_{i=1}^{lfloorfrac{min(n,m)}{x} floor}mu(i) imes {lfloorfrac{lfloorfrac{n}{x} floor}{i} floor} imes {lfloorfrac{lfloorfrac{m}{x} floor}{i} floor})
预处理出(mu(i))的前缀和即可(O(sqrt{n}))回答每次询问。总复杂度(O(n+sqrt{n})).
例题1：YY的GCD
求：
多组测试数据，(1leq n,mleq 10^7,1leq Tleq 10^4).
( ext{原式}=displaystylesum_{i=1}^{n}sum_{j=1}^{m}sum_{pin prime}[gcd(i,j)=p])
(=displaystylesum_{pin prime}sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=p])
(=displaystylesum_{pin prime}sum_{i=1}^{lfloorfrac{n}{p} floor}sum_{j=1}^{lfloorfrac{m}{p} floor}[gcd(i,j)=1])
设(f(n,m,x)=displaystylesum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=x]).
设(g(n,m,x)=displaystylesum_{x|d}f(n,m,d)).
则(g(n,m,x)=displaystylesum_{i=1}^{n}sum_{j=1}^{m}[x|gcd(i,j)])
(=displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}sum_{j=1}^{lfloorfrac{m}{x} floor}[1|gcd(i,j)])
显然对于任意(i,jinmathbb{N_+})，([1|gcd(i,j)])成立，所以(g(n,m,x)={lfloorfrac{n}{x} floor}{lfloorfrac{m}{x} floor}).
所以(f(n,m,x)=displaystylesum_{x|d}mu(frac{d}{x})g(n,m,d))
则我们要求的是(displaystylesum_{pin prime}f(lfloorfrac{n}{p} floor,lfloorfrac{m}{p} floor,1))
(=displaystylesum_{pin prime}sum_{d=1}^{n}mu(d)lfloorfrac{n}{dp} floorlfloorfrac{m}{dp} floor)
这个(dp)比较丑，我们把它换成(i)，得到
(displaystylesum_{i=1}^{n}lfloorfrac{n}{i} floorlfloorfrac{m}{i} floorsum_{pin prime,p|i}mu(frac{i}{p})).
后面(displaystylesum_{pin prime,p|i}mu(frac{i}{p}))我们是可以提前预处理出来的，这样用整除分块就可以(O(sqrt{n}))回答每次询问了。
例题2：[SDOI2015]约数个数和
定义(d(x))为(x)的约数个数。
求：
多组测试数据，(1leq n,m,Tleq 5 imes 10^4).
初步转化：
证明：设(ij=displaystyleprod_{t} p_t^{e_t})，对于任意一个(p_t)，设(i)对(e_t)的贡献为(a)，(j)对(e_t)的贡献为(b)，即(a+b=e_t)。对于一个(ij)的一个约数(w)：如果(w)里(p_t)的次数(cleq a)，我们在(i)里计算它；否则，我们在(j)里计算(c-a)。即：(x)里一个(p^c)表示当前(ij)的这个因数里有(p^c)；(y)里一个(p^c)表示当前(ij)的这个因数里有(p^{c+a})。这样只要(x,y)互质，就保证了不重不漏的计数。
接下来我们就可以快乐地推式子了。
原式(=displaystylesum_{i=1}^{n}sum_{j=1}^{m}sum_{x|i}sum_{y|j}[gcd(x,y)=1])
交换和式：
(=displaystylesum_{x=1}^{n}sum_{y=1}^{m}sum_{i=1}^{lfloorfrac{n}{x} floor}sum_{j=1}^{lfloorfrac{n}{y} floor}[gcd(x,y)=1])
(=displaystylesum_{x=1}^{n}sum_{y=1}^{m}{lfloorfrac{n}{x} floor}{lfloorfrac{n}{y} floor}[gcd(x,y)=1])
开始反演。（把(x,y)换成(i,j)使式子更好看一点）
设(g(x)=displaystylesum_{x|d}f(d))
(=displaystylesum_{i=1}^{n}sum_{j=1}^{m}lfloorfrac{n}{i} floorlfloorfrac{m}{j} floor[x|gcd(i,j)])
(=displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}sum_{j=1}^{lfloorfrac{m}{x} floor}lfloorfrac{n}{xi} floorlfloorfrac{m}{xi} floor)
代回去：(f(x)=displaystylesum_{x|d}mu(frac{d}{x})g(d))
我们要求的其实是：(f(1)=displaystylesum_{i=1}^{n}mu(i)g(i)).
我们在(O(nsqrt{n}))的时间内，枚举每个(x)并预处理出(s(x)=displaystylesum_{i=1}^{x}lfloorfrac{x}{i} floor)的值。
则答案就是(f(1)=displaystylesum_{i=1}^{n}mu(i)s(lfloorfrac{n}{i} floor)s(lfloorfrac{m}{i} floor))，预处理出(mu)的前缀和即可用整除分块(O(sqrt{n}))回答询问。
例题3：bzoj2693 jzptab
求：
多组测试数据，(1leq n,mleq 10^7,1leq Tleq 10^4).
这题有个弱化版，没有多测。我们从这里讲起。
原式(=displaystylesum_{i=1}^{n}sum_{j=1}^{m}frac{ij}{gcd(i,j)})
(=displaystylesum_{i=1}^{n}sum_{j=1}^{m}sum_{k=1}^{min(n,m)}frac{ij}{k}[gcd(i,j)=k])
(=displaystylesum_{k=1}^{min(n,m)}sum_{i=1}^{lfloorfrac{n}{k} floor}sum_{j=1}^{lfloorfrac{m}{k} floor}ijk[gcd(i,j)=1])
(=displaystylesum_{k=1}^{min(n,m)}ksum_{i=1}^{lfloorfrac{n}{k} floor}sum_{j=1}^{lfloorfrac{m}{k} floor}ij[gcd(i,j)=1])
套用莫比乌斯反演。
设(f(n,m,x)=displaystylesum_{i=1}^{n}sum_{j=1}^{m}ij[gcd(i,j)=1]).
设(g(n,m,x)=displaystylesum_{x|d}f(n,m,d)).
则(g(n,m,x)=displaystylesum_{i=1}^{n}sum_{j=1}^{m}ij[x|gcd(i,j)])
(=x^2displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}sum_{j=1}^{lfloorfrac{m}{x} floor}ij[1|gcd(i,j)])
(=x^2displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}sum_{j=1}^{lfloorfrac{m}{x} floor}ij)
把(i)提到前面，得到：
(=x^2displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}isum_{j=1}^{lfloorfrac{m}{x} floor}j)
等差数列求和：
(=x^2displaystylesum_{i=1}^{lfloorfrac{n}{x} floor}ifrac{{lfloorfrac{m}{x} floor} imes ({lfloorfrac{m}{x} floor}+1)}{2})
(=x^2frac{{lfloorfrac{n}{x} floor} imes ({lfloorfrac{n}{x} floor}+1)}{2}cdotfrac{{lfloorfrac{m}{x} floor} imes ({lfloorfrac{m}{x} floor}+1)}{2})
代回去得到：
(f(n,m,x)=displaystylesum_{x|d}mu(frac{d}{x})g(n,m,d))
(f(lfloorfrac{n}{k} floor,lfloorfrac{m}{k} floor,1)=displaystylesum_{i=1}^{lfloorfrac{n}{k} floor}mu(i)cdot i^2cdot frac{{lfloorfrac{n}{ki} floor} imes ({lfloorfrac{n}{ki} floor}+1)}{2}cdotfrac{{lfloorfrac{m}{ki} floor} imes ({lfloorfrac{m}{ki} floor}+1)}{2})
于是我们就可以(O(sqrt{n}))计算(f(n,m,k)).
所以，原式(=displaystylesum_{k=1}^{n}k imes f(lfloorfrac{n}{k} floor,lfloorfrac{m}{k} floor,1))，就可以在(O(sqrt{n}) imes O(sqrt{n})=O(n))的时间内算出了。
然后来看bzoj这个题。因为要多测，我们(O(n))的复杂度不够优秀。
为了方便，我们设(S(i,j)=sum_{i=1}^{n}sum_{j=1}^{m}ij).
则原式(=displaystylesum_{k=1}^{n}ksum_{i=1}^{lfloorfrac{n}{k} floor}mu(i)cdot i^2cdot S(lfloorfrac{n}{ki} floor,lfloorfrac{m}{ki} floor)).
设(T=ki)，把(S(lfloorfrac{n}{ki} floor,lfloorfrac{m}{ki} floor))提前，可得：
(displaystylesum_{T=1}^{n}S(lfloorfrac{n}{T} floor,lfloorfrac{m}{T} floor)sum_{i|T}mu(i)cdot i^2cdotfrac{T}{i})
(=displaystylesum_{T=1}^{n}S(lfloorfrac{n}{T} floor,lfloorfrac{m}{T} floor)sum_{i|T}mu(i)cdot icdot T)
后面的部分(f(T)=displaystylesum_{i|T}mu(i)cdot icdot T)显然是一个积性函数，所以我们考虑用线性筛将它预处理出来。
-
当(n=1)时，显然有(f(n)=1)。
-
当(n)为素数时，显然有(f(n)=n-n^2)。
-
当(n)为合数时，设(n=icdot p_j)（(p_j)是质数）。如果(p_j|i)，那么(mu(icdot p_j))一定为(0)，也就是说没有新增项。因此(f(icdot p_j))相较于(f(i))而言只是每项中的(T)变了，所以(f(n)=f(i)cdot p_j)。
预处理出(f)的前缀和后我们就可以(O(sqrt{n}))回答每次询问了。