狄利克雷卷积&莫比乌斯反演

设\(n,m\)互质：

由于\(n,m\)互质，其因数也互质，所以所有因数的组合不重不漏地构成了\(nm\)的因数集合。

由于\(\varphi\)是积性函数，只需证明\(k=1\)的时候\(\operatorname{id}=\varphi*1\)成立即可。设此时\(n=p^a\)。

由于当\(n,m\)互质时，其因数除了1无交集，有：

则对于一般情况而言，将\(n\)按照质因数分解相乘即可证明\(\operatorname{id}=\varphi*1\)。
两边同时卷上\(\mu\)即可得到:

\(n=1\)时，正确性显然。

直接从区间考虑不方便，不妨直接考虑做前缀和和做差，再进行一个容斥。

这时候前面证的性质就要派上用场了。由于\(\lfloor\frac{n}{x}\rfloor\)的取值一定是连续的，我们可以将相同的值合并到同一块中计数。从前面取整函数的性质可知，使得\(\lfloor\frac{n}{x}\rfloor=\lfloor\frac{n}{y}\rfloor\)的最大\(x=\lfloor\frac{n}{\lfloor\frac{n}{y}\rfloor}\rfloor\)。这样就可以根据取值的不同来分块，利用前缀和相减再乘上一个相同的系数来计数。
又由前面所证明的，\(\lfloor\frac{n}{d}\rfloor\)的取值不超过\(2\sqrt{n}\)个，所以一次计数的时间复杂度为\(O(\sqrt{n})\)。
这就是数论分块。
至于容斥，很简单啦，理解成二维前缀和或其它方法都可以。

#include 
#include 
const int maxn=5e4+10;
int s[maxn],mu[maxn],prim[maxn];
int tot;
bool vis[maxn];

void swap(int &x,int &y) {x^=y^=x^=y;}
int min(int x,int y) {return xm)
		swap(n, m);
	int res=0;
	for (int l=1,r=1;l<=n;l=r+1)
	{
		r=min(n/(n/l), m/(m/l));
		res+=(s[r]-s[l-1])*(n/l)*(m/l);
	}
	return res;
}
int main()
{
	int n=read();
	prework(5e4);
	for (int i=1;i<=n;i++)
	{
		int a=read(),b=read(),c=read(),d=read(),k=read();
		printf("%d\n",solve(b/k, d/k)-solve((a-1)/k, d/k)-solve((c-1)/k, b/k)+solve((a-1)/k, (c-1)/k));
	}
	return 0;
}

只需要预处理一下\(\sum_{i=1}^n i\)和\(\sum_{i=1}^ni^2\mu(i)\)，再进行数论分块，本题就得到了解决。

#include 
#include 
typedef long long ll;
const int maxn=1e7+10;
const int p=20101009;
int mu[maxn],prim[maxn],s[maxn],t[maxn];
int tot;
bool vis[maxn];

void swap(int &x,int &y) {x^=y^=x^=y;}
int min(int x,int y) {return x=p)
			s[i]-=p;
		else if (s[i]<0)
			s[i]+=p;
		for (int j=1;j<=tot&&i*prim[j]<=n;j++)
		{
			vis[i*prim[j]]=1;
			if (i%prim[j]==0)
			{
				mu[i*prim[j]]=0;
				break;
			}
			mu[i*prim[j]]=-mu[i];
		}
	}
	for (int i=1;i<=n;i++)
	{
		t[i]=t[i-1]+i;
		if (t[i]>=p)
			t[i]-=p;
		else if (t[i]<0)
			t[i]+=p;
	}
}
int main()
{
	int n=read(),m=read();
	if (n>m)
		swap(n, m);
	prework(m);
	int ans=0;
	for (int d=1;d<=n;d++)
	{
		int sum=0;
		for (int l=1,r=1;l<=n/d;l=r+1)
		{
			r=min(n/d/(n/d/l), m/d/(m/d/l));
			sum+=(ll)(s[r]-s[l-1])*t[n/l/d]%p*t[m/l/d]%p;
			if (sum>=p)
				sum-=p;
			else if (sum<0)
				sum+=p;
		}
		ans+=(ll)sum*d%p;
		if (ans>=p)
			ans-=p;
		else if (ans<0)
			ans+=p; 
	}
	printf("%d\n",ans);
	return 0;
}

首先，\(\operatorname{d}(ij)\)当然不可能用\(\operatorname{d}=1*1\)来求。转换思路，\(ij\)的因数相当于是由\(i\)因数集合中的元素以及\(j\)因数集合中的元素相乘而得到的，为了使计数不重不漏，应限制相乘的两个元素互质。
因此得到了\(\operatorname{d}(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\)，有个经常见到的东西就出现了。
代入式子：

#include 
#include 
typedef long long ll;
const int maxn=5e4+10;
int mu[maxn],prim[maxn];
int tot;
ll s[maxn],t[maxn];
bool vis[maxn];

void swap(int &x,int &y) {x^=y^=x^=y;}
int min(int x,int y) {return xm)
			swap(n, m);
		ll ans=0;
		for (int l=1,r=1;l<=n;l=r+1)
		{
			r=min(n/(n/l), m/(m/l));
			ans+=(s[r]-s[l-1])*t[n/l]*t[m/l];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

先讲一个稍微麻烦一点的。（不管麻不麻烦最后都是用杜教筛的，你看看这数据范围哪是线性筛能跑得动的）

到这一步你会发现这跟之前有道题非常相似，但是那个数据范围\(O(n\sqrt{n})\)能过而本题不行。所以还要进行下一步转化。
设\(t_n=(\sum_{i=1}^{n}i)^2=\frac{(1+n)^2 n^2}{4}\)。

\(t\)很好解决，但是\(i^2\varphi(i)\)不数论分块这日子就过不下去了。下面就得用到杜教筛。
设\(f(i)=i^2 \varphi(i),s(n)=\sum_{i=1}^n f(i)\)，\(f\)显然为积性函数。根据杜教筛，我们需要找到一个易于计算的\(g\)使得\(h=f*g\)也较为好算，通过\(g(1)s(n)=\sum_{i=1}^n h(i)-\sum_{j=2}^n g(j)s(\lfloor\frac{n}{j}\rfloor)\)即可数论分块求出\(s\)，再套回原式中进行数论分块。
观察\(\sum_{d|n}d^2\varphi(d) g(\frac{n}{d})\)会觉得这个\(d^2\)非常的碍眼，想办法将它消成常数再卷\(\varphi\)（我们已经知道了\(\operatorname{id}=\varphi *1\)，所以这会是一个比较自然的想法)。
不如将\(g(x)\)设为\(x^2\)，恰好能使\(h(n)=\sum_{d|n}d^2\varphi(d) g(\frac{n}{d})=n^2\sum_{d|n}\varphi(d)=n^3\)。而\(n^3\)的和又是可以\(O(1)\)实现的，其表达式可以用拉格朗日插值法等方法得到，最后得到\(\sum_{i=1}^n h(i)=\frac{(1+n)^2n^2}{4}=t(n)\)。数论分块时还需要用到\(\sum_{i=1}^n i=\frac{n(n+1)(2n+1)}{6}\)。
于是\(s(n)=t(n)-\sum_{j=2}^n j^2 s(\lfloor\frac{n}{j}\rfloor)\)，可以很快地递推出所有取值的\(s(\lfloor\frac{n}{d}\rfloor)\)。又因为\(n\)在这里和原式中没有变化，所以可以很方便地把\(s(\lfloor\frac{n}{d}\rfloor)\)代回原式中，所需要的值不多不少刚刚好。
具体实现看代码，命名方式与上述相同。

另一种呢，其实本质差不多，只不过变换的角度是从\(\operatorname{id}=\varphi*1\)出发的。

接下来要做的，你应该都知道了：想办法对\(d^2\varphi(d)\)做杜教筛。
代码就不写了，差不多的，下面放的是上一个做法的代码。

#include 
#include 
#include 
#include