Problem

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

Sub problem

设 Ans(i,j) 表示有多少个数对(x,y)，满足x≤i，c≤y≤j，且gcd(x,y) = k。 我们可以先求出 Ans(b,d),Ans(b,c−1),Ans(a−1,d),Ans(a−1,c−1) ， 然后 ans=Ans(b,d)−Ans(b,c−1)−Ans(a−1,d)+Ans(a−1,c−1) 。

那么问题就变成了如何求 Ans(n,m) 。

Discuss

讨论一下 Ans(n,m) 如何求，其中 n<m 。 先设 f(k) ，表示有多少个数对(x,y)，满足x≤n，c≤y≤m，且gcd(x,y) = k。 显然 Ans(n,m)=f(k) 。

再设 g(k) ，表示多少个数对(x,y)，满足x≤n，c≤y≤m，且k|gcd(x,y) 因为 k|gcd(x,y) ，所以设 x=k∗x′,y=k∗y′ ； 由于 x′ 只能取 1...⌊nk⌋ ， y′ 只能取 1...⌊mk⌋

所以

g(k)=⌊nk⌋∗⌊mk⌋

同时，我们会有

g(k)=∑i=1⌊nk⌋f(i∗k)(1)

此时，我们将 g(k) 用 f(k) 表示，并且 g(k) 是容易求出结果的。

---

Mobius

正片开始

我们非常功利地得出结论： 正当我们遇到这种式子时，

g(i)=∑d|if(d)(2) 或 g(i)=∑j=1⌊nk⌋f(i∗j)(3) 当 g[d] 是 积性函数，我们可以将上式转化为， f(i)=∑d|ig(d)∗μ(id) f(i)=∑j=1⌊nk⌋g(i∗j)∗μ(j) 其中 μ(x)=⎧⎩⎨⎪⎪1,(−1)k,0,x=1x=∏ki=1pi,pi∈Potherwise

---

Discuss： μ 的性质

（1） μ 是积性函数 可以证明， μ 函数也是积性函数，所以 μ 可以通过线性筛法预处理，如下代码。

miu[1]=1; for (i=2;i<maxn;i++){ if (!bz[i]){ p[++p[0]]=i; miu[i]=-1; } for (j=1;j<=p[0];j++){ k=i*p[j]; if (k>=maxn) break; bz[k]=true; if (i%p[j]==0){ miu[k]=0; break; }else miu[k]=-miu[i]; } }

（2） μ 的“和性质”

∑d|nμ(d)={0,1,n=1n>1

Back to the Problem

题目的式子是

g(k)=∑i=1⌊nk⌋f(i∗k)(1) 跟 (2) 有异曲同工之妙， 所以 f(k)=∑i=1⌊nk⌋g(i∗k)∗μ(i)=∑i=1⌊nk⌋⌊nik⌋∗⌊mik⌋∗μ(i) 然而，这并没有什么卵用，我们仍然过不了。 还能优化？？

Deeplier discuss

我们发现， 其实 ⌊nik⌋∗⌊mik⌋ 很多时候是相同的取值。 所以我们可以将相同值的 ⌊nik⌋∗⌊mik⌋ 合并一起来计算，来优化时间复杂度。 显然 ⌊nik⌋ 的取值最多有 2∗n√ 种， 所以可以把时间复杂度优化到 O(2∗n√+2∗m−−√) 一次询问。

Ending

至此，我们已解决了这道题。 原题Code。

Proving

μ 的“和性质”

求证：

∑d|nμ(d)={0,1,n=1n>1 证明： n=1 时显然； 讨论 n>1 的情况， 因为 μ 的定义， μ(x)=⎧⎩⎨⎪⎪1,(−1)k,0,x=1x=∏ki=1pi,pi∈Potherwise 所以 ∑d|nμ(d) 中，只有当 d 的任意质因子的指数不能超过1时， μ(d) 才会对 和产生贡献。 我们设 n 的质因子个数为q个。 那么， ∑d|nμ(d)=∑i=0qCiq∗(−1)i 我们观察一下杨辉三角： 11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1... 显然的是，当 q 是偶数时，由杨辉三角的对称性，∑d|nμ(d)=∑i=0qCiq∗(−1)i=0 现在考虑 q(q>1) 是奇数的情况， ∑i=0qCiq∗(−1)i=C0q−Cqq+∑i=1q−1Ciq∗(−1)i=C0q−Cqq+∑i=1q−1(Ci−1q−1+Ciq−1)∗(−1)i=C0q−Cqq+∑i=1q−1Ci−1q−1∗(−1)i+∑i=1q−1Ciq−1∗(−1)i=∑i=0q−1Ciq−1∗(−1)i+1+∑i=0q−1Ciq−1∗(−1)i 由 q−1 是偶数，综上， ∑d|nμ(d)=∑i=0qCiq∗(−1)i=0 得证。

证明反演

求证：

g(i)=∑d|if(d)⇒f(i)=∑d|ig(d)∗μ(id) 证明： ∑d|ig(d)∗μ(id)=∑d|iμ(id)∑d′|df(d′) 这里经历一个重要的过程：转换主体， 感性地想，所有的 μ(id) 都与 f(d′) 相乘过，其中 d′|d ； 反过来，那么所有的 f(d′) 都与 μ(id) 相乘过，其中 d′|d 。 所以， ∑d|iμ(id)∑d′|df(d′)=∑d′|if(d′)∑d′|d,d|iμ(id) 令 x=id ，则 d=ix ，那么 ∑d′|if(d′)∑d′|d,d|iμ(id)=∑d′|if(d′)∑d′|ix,ix|iμ(x)=∑d′|if(d′)∑x|id′μ(x) 由 μ 的“和性质”， 当 d′!=i 时，则 id′>1 ，所以 ∑x|id′μ(x)=0 ； 当 d′=i 时，则 id′=1 ，所以 ∑x|id′μ(x)=1 。 所以 ∑d|if(d)∗μ(id)=∑d′|if(d′)∑x|id′μ(x)=f(i) 综上， f(i)=∑d|ig(d)∗μ(id) 得证。

---

另一个变式 (3) 类似。

True Ending

至此，Mobius反演已证明完毕。