自动搬运

查看原文

来自洛谷，原作者为

	Spasmodic 182375

搬运于2025-08-24 22:24:12，当前版本为作者最后更新于2020-08-18 19:57:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

验题人写的一个题解，感觉比出题人的式子简单多了，而且用不着莫反。

$$\sum_{i\le n}\sum_{j\le m}\tau(i)\tau(j)\tau(\gcd(i,j)) $$

考虑$\tau$的定义，有：

$$=\sum_{i\le n}\sum_{j\le m}\tau(i)\tau(j)\sum_{k|i,k|j}1 $$

枚举$k$：

$$=\sum_k\sum_{k|i,i\le n}\tau(i)\sum_{k|j,j\le m}\tau(j) $$

设

$$S_n(k)=\sum_{k|i,i\le n}\tau(i)$$

则

$$(*)=\sum_kS_n(k)S_m(k)$$

式子推完了！

先在 $O(n\log n)$ 时间内暴力预计算出 $\tau(i),1\le i\le n$，然后可以在 $O(n\log n)$ 时间内暴力预计算出 $S_n(k),S_m(k)$，总复杂度 $O(n\log n)$。

放个代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m,p,d[N],ans;
void init(int n){
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=i)
			d[j]++;
}
inline int calc(int n,int k){
	int ret=0;
	for(int i=k;i<=n;i+=k)ret=(ret+d[i])%p;
	return ret;
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	if(n>m)swap(n,m);
	init(m);
	for(int i=1;i<=n;i++)ans=(ans+1LL*calc(n,i)*calc(m,i)%p)%p;
	printf("%d\n",ans);
	return 0;
}