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)用f(k)表示，并且g(k)是容易求出结果的。

Mobius

正片开始

我们非常功利地得出结论：

正当我们遇到这种式子时，

或

当g[d]是积性函数，我们可以将上式转化为，

其中

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）μ的“和性质”

Back to the Problem

题目的式子是

跟(2)有异曲同工之妙，

所以

然而，这并没有什么卵用，我们仍然过不了。

还能优化？？

Deeplier discuss

我们发现，

其实⌊nik⌋∗⌊mik⌋很多时候是相同的取值。

所以我们可以将相同值的⌊nik⌋∗⌊mik⌋合并一起来计算，来优化时间复杂度。

显然⌊nik⌋的取值最多有2∗n√种，

所以可以把时间复杂度优化到O(2∗n√+2∗m−−√)一次询问。

Ending

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

原题Code。

Proving

μ的“和性质”

求证：

证明：

n=1时显然；

讨论n>1的情况，

因为μ的定义，

所以∑d|nμ(d)中，只有当d的任意质因子的指数不能超过1时，μ(d)才会对和产生贡献。

我们设n的质因子个数为q个。

那么，

我们观察一下杨辉三角：

显然的是，当q是偶数时，由杨辉三角的对称性，

现在考虑q(q>1)是奇数的情况，

由q−1是偶数，综上，

得证。

证明反演

求证：

证明：

这里经历一个重要的过程：转换主体，

感性地想，所有的μ(id)都与f(d′)相乘过，其中d′|d；

反过来，那么所有的f(d′)都与μ(id)相乘过，其中d′|d。

所以，

令x=id，则d=ix，那么

由μ的“和性质”，

当d′!=i时，则id′>1，所以∑x|id′μ(x)=0；

当d′=i时，则id′=1，所以∑x|id′μ(x)=1。

所以

综上，

得证。

另一个变式(3)类似。

True Ending

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