问题

给出 $n,m$（$1 \leq n,m \leq 10^7$），求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=1]$，即：满足 $1 \leq i \leq n$，$1 \leq j \leq m$，且 $\gcd(i,j)=1$ 的二元组 $(i,j)$ 的数量。

题解

一、莫比乌斯函数介绍

设函数 $\mu(d)$ 满足以下条件：

$$\mu(d) \begin{cases} 1或-1 &\text{如果d不含重复质因子（质因子个数为奇数则为-1，否则为1）} \\ 0 &\text{如果d含有重复质因子} \end{cases}$$

那么有：

$$\sum\limits_{d|n}\mu(d) \begin{cases} 1 &\text{如果 $n=1$} \\ 0 &\text{如果 $n>1$} \end{cases}$$

证明：

当 $n=1$ 得证。

当 $n>1$ ， $n={p_1}^{a_1}*{p_2}^{a_2}*{p_3}^{a_3}* \dots *{p_k}^{a_k}$ 设: $n'={p_1}*{p_2}*{p_3}* \dots *{p_k}$，则有： $\sum\limits_{d\|n}\mu(d)=\sum\limits_{d\|n'}\mu(d)=0$

1、为什么 $\sum\limits_{d\|n}\mu(d)=\sum\limits_{d|n'}\mu(d)$ ？明明 $\sum\limits_{d |n}\mu(d)$ 比 $\sum\limits_{d |n'}\mu(d)$ 多好多项。

答：多出来的 $\mu(d)$ 都是零。多出来的 $\mu(d)$ 中的 $d$ 都是包含重复质因子的。

2、哦，那为什么 $\sum\limits_{d|n'}\mu(d)=0$ 呢？

答：因 $d | n'$ ，故 $d={p_1}^{0|1}*{p_2}^{0|1}*{p_3}^{0|1}* \dots *{p_k}^{0|1}$，可知 $d$ 总共有 $2^k$ 个。

即： $\sum\limits_{d|n'}\mu(d)=\mu(d_1)+\mu(d_2)+\mu(d_3)+ \dots +\mu(d_{2^k})$ 对所有的 $d$ 按包含的质因子的个数进行分类。 包含0个质因子的 $d$ 的个数：${k \choose 0}$ 个，就是 $d=1$，这类 $\mu(d)=1=(-1)^0$。

包含1个质因子的 $d$ 的个数：${k \choose 1}$ 个，这类 $\mu(d)=-1=(-1)^1$。

包含2个质因子的 $d$ 的个数：${k \choose 2}$ 个，这类 $\mu(d)= 1=(-1)^2$。

包含3个质因子的 $d$ 的个数：${k \choose 3}$ 个，这类 $\mu(d)=-1=(-1)^3$。

$\dots$

包含k个质因子的 $d$ 的个数：${k \choose k}$ 个，这类 $\mu(d)=-1=(-1)^k$。

故：$\sum\limits_{d|n'}\mu(d)={k \choose 0}*(-1)^0+{k \choose 1}*(-1)^1+{k \choose 2}*(-1)^2+ \dots +{k \choose k}*(-1)^k$

联想： $(1+x)^k={k \choose 0}*x^0+{k \choose 1}*x^1+{k \choose 2}*x^2+ \dots +{k \choose k}*x^k$

可得： $\sum\limits_{d|n'}\mu(d)=(1+ {-1})^k=0$

得证。

二、本题推导过程

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lbrack\gcd(i,j)=1\rbrack$
$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d | \gcd(i,j)}\mu(d)$	注：$\lbrack\gcd(i,j)=1\rbrack$ 变成 $\sum\limits_{d | \gcd(i,j)} \mu(d)$ 是 黄金变换操作。黄金？宝贵，重要的意思。 吐槽：好好好！本来两层for，现在变成三层for，怎么变得越来越复杂了？
$=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d=1}^n \lbrack d | i \rbrack \lbrack d | j \rbrack \mu(d)$	注：$\sum\limits_{d|\gcd(i,j)}\mu(d)$ 变为 $\sum\limits_{d=1}^n \lbrack d | i \rbrack \lbrack d | j \rbrack \mu(d)$ 是银变换操作。
$=\sum\limits_{d=1}^n \mu(d)\sum\limits_{i=1}^n\lbrack d | i \rbrack \sum\limits_{j=1}^m\lbrack d | j \rbrack$	注：调换for循环的顺序, $\lbrack d|i\rbrack$ 表示 $i$ 是 $d$ 的倍数时+1，故 $\sum\limits_{i=1}^n\lbrack d | i \rbrack$ 等于 $\lfloor \frac{n}{d} \rfloor$
$=\sum\limits_{d=1}^n\mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d}\rfloor$	注： $\sum\limits_{i=1}^n\lbrack d | i \rbrack 变为 \lfloor \frac{n}{d} \rfloor$ 铜变换操作。 回应吐槽：增加一层for循环，多了两项： $\lfloor \frac{n}{d} \rfloor$ 和 $\lfloor \frac{m}{d}\rfloor$，就是为了消灭 $\sum\limits_{i=1}^n$ 和 $\sum\limits_{j=1}^m$。总结：增加一层for，消灭两层for。

到此，在 $\sum\limits_{d=1}^n$ 中 $\mu(d)$ 可以前缀和， $\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d}\rfloor$ 可以分块加速即可，从而避免了 $d$ 逐个枚举 $1 \dots n$。 注：

具体过程如下：

具体代码如下：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7;
int pr, p[N+10];LL mu[N+10]; bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
    for(int i=2;i<=N;i++)
	{
        if(!v[i]) p[++pr]=i, mu[i]=-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
		{
            v[i*p[j]]=true;
            if(i%p[j]==0){mu[i*p[j]]=0;break;}
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++) mu[i]+=mu[i-1];
}
LL calc(int n, int m)
{
    if(n>m)swap(n,m);
	LL ans=0;
    for(int l=1,r;l<=n;l=r+1)
	{
        r=min(n/(n/l), m/(m/l));
        ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);
    }
    return ans;
}
int main()
{
	init();
	int T,n,m;scanf("%d",&T);
	while(T--)
	{
        scanf("%d%d",&n,&m);
        printf("%lld\n",calc(n,m));
	}
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7;
int pr/*质数个数*/, p[N + 10]/*第i个质数*/;
LL mu[N + 10]/*
mu[i] = 0  有重复的质因子
mu[i] = -1 无重复质因子，质因子个数为奇数
mu[i] = 1  无重复质因子，质因子个数为偶数 
*/;
bool v[N + 10]/*0是质数，1不是质数*/;

void init()
{
	memset(v, 0, sizeof v);
	pr = 0; mu[0] = 0; mu[1] = 1;
	for (int i = 2; i <= N; i++)
	{
		if (!v[i]/*i没被标记, 是质数*/)
			p[++pr] = i/*发现新质数*/, mu[i] = -1/*只有i一个质因子*/;
		for (int j = 1; j <= pr/*依次乘以已发现的质数*/ and p[j] * i <= N; j++)
		{
			v[i * p[j]] = true/*标记*/;
			if (i % p[j] == 0/*找到自己的质因子*/)
				{ mu[i * p[j]] = 0/*出现p[j]这个重复的质因子*/; break; }
			mu[i * p[j]] = -mu[i]/*多了p[i]这个质因子，故取相反数*/;
		}	 
	}
	for (int i = 1; i <= N; i++) mu[i] += mu[i - 1];/*处理前缀和*/
}

LL calc(int n, int m)
{
	if (n > m) swap(n, m);
	LL ans = 0;
	for (int l = 1, r; l <= n; l = r + 1)/*分块加速*/
	{
		r = min(n / (n / l), m / (m / l));
		ans += (mu[r] - mu[l - 1]) * (n / l) * (m / l); 
	}
	return ans;
}

int main()
{
	init();
	int T, n, m; cin >> T;
	while (T--)
	{
		cin >> n >> m;
		cout << calc(n, m) << '\n';
	}
	return 0;
}

#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e7+10; int pr,p[N],mu[N]; bool v[N]; void init(){ memset(v,0,sizeof(v)); pr=0; mu[0]=0; mu[1]=1; for(int i=2;i<=N;i++) { if(!v[i]){ p[++pr]=i; mu[i]=-1; } for(int j=1;j<=pr&&ip[j]<=N;j++) { v[ip[j]]=1; if(i%p[j]==0) { mu[ip[j]]=0; break; } mu[ip[j]]=-mu[i]; } } for(int i=1;i<=N;i++) { mu[i]+=mu[i-1]; } } int calc(int n,int m) { int ans=0; if(n>m) { swap(n,m); } for(int l=1,r;l<=n;l=r+1) { r=min(m/(m/l),n/(n/l)); ans+=(mu[r]-mu[l-1])(m/l)(n/l); } return ans; } signed main(){ init(); int t; scanf("%lld",&t); while(t--) { int n,m; scanf("%lld%lld",&n,&m); printf("%lld\n",cal(n,m)); } return 0; }

fxy没妈

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10;
int pr,p[N],mu[N];bool v[N];
void init(){
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!v[i])p[++pr]=i,mu[i]=-1;
		for(int j=1;j<=pr&&i*p[j]<=N;j++){
			v[i*p[j]]=1;
			if(i%p[j]==0){mu[i*p[j]]=0;break;}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
int cal(int n,int m){
	int ans=0;
	if(n>m)swap(n,m);
	for(int l=1,r;l<=n;l=r+1){
		r=min(m/(m/l),n/(n/l));
		ans+=(mu[r]-mu[l-1])*(m/l)*(n/l);
	}
	return ans;
}
signed main(){
	init();
	int t;scanf("%lld",&t);
	while(t--){
		int n,m;scanf("%lld%lld",&n,&m);
		printf("%lld\n",cal(n,m));
	}
	return 0;
}

除法分块加速题目直通链接

洛谷同题

都给我点差评！！！