自动搬运

查看原文

来自洛谷，原作者为

	黑影洞人 向最美好的前途，哪怕漫漫长路

搬运于2025-08-24 22:00:18，当前版本为作者最后更新于2022-07-02 20:10:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一种超短的做法

我们设 $f(d)$ 为 $1≤a≤A,1≤b≤B$ 中 $\gcd(a,b)=d$ 的二元组个数。

如何求 $f(d)$ 成为本题的关键，我将用计数DP来解决。

我们打一个表观察一下 $\gcd(a,b)$。

1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 1 3 1 1 3 1 1 3 1
1 2 1 4 1 2 1 4 1 2
1 1 1 1 5 1 1 1 1 5
1 2 3 2 1 6 1 2 3 2
1 1 1 1 1 1 7 1 1 1
1 2 1 4 1 2 1 8 1 2
1 1 3 1 1 3 1 1 9 1
1 2 1 2 5 2 1 2 1 10

我们设函数 $g(d)$ 是 $\sum_{(a,b)}d| \gcd(a,b)$。

如图，可以很直观的发现 $g(d)$ 实际上就是 $(A/d)*(B/d)$。

我们可以很直观的发现，$g(d)=f(d)+f(2d)+f(3d)……+f(\lfloor \frac{n}{d} \rfloor*d)$。

于是我们反向推一下 $f(d)=g(d)- f(2d)-f(3d)……-f(\lfloor \frac{n}{d} \rfloor*d)$ , 并且有边界条件 $g(n)=f(n)=1$。

于是我们就得到了 $f(d)$ 的逆推式。

上代码：

#include<cstdio>
#include<algorithm>
#define int long long
#define N 100000006
using namespace std;
int k,g[N],f[N],ans,n,m,sum,Ch;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&Ch);
	if(n>m)swap(n,m);
	for(int k=n;k>=1;k--){
		g[k]=(n/k)*(m/k);
		f[k]=g[k];
		for(int j=2;j<=(n/k);j++)f[k]-=f[j*k];
	}
	printf("%lld",f[Ch]);
	return 0;
}

算法时间复杂度为 $O(nH(n))$，其中 $H(n)$ 为调和级数和，求一下积分可以知道时间复杂度约为 $O(n \ln n)$