洛谷P2257 莫比乌斯反演+线性筛

题意：

给出$n,m$，计算有多少$i\in [1,n],j\in [1,m]$，使得$gcd(i,j)$是一个素数

Solution：

不妨转化为枚举这个素数，找有多少对满足条件
$$\sum _{p\in prime}\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)=p]$$
凑出莫比乌斯反演的形式，得到
$$\sum _{p\in prime}\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\sum _{d|gcd(i,j)}\mu (d)$$
优先枚举因子，并且设$n\le m$
$$\sum _{p\in prime}\sum _{d=1}^{\lfloor \frac{n}{p}\rfloor }\mu (d)\lfloor \frac{n}{pd}\rfloor \lfloor \frac{m}{pd}\rfloor$$
优先枚举乘积，然后就可以将一部分转化为枚举因子，这里枚举$T=pd$
$$\sum _{T=1}^n\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \sum _{p\in prime,p|T}\mu (\frac{T}{p})$$
前面的部分可以数论分块解决，现在只需要快速求得
$$f(T)=\sum _{p\in prime,p|T}\mu (\frac{T}{p})$$
可以线性筛筛出这个函数，线性筛关键在于添加一个质因子会带来什么后果，这里我们假设给$T$加上一个质因子$p$

有关莫比乌斯函数，不妨先假设$T$的唯一分解为：
$$T=p_1^{a_1}{p}_2^{a_2}...p_n^{a_n}$$

• 如果$T$包含了$p$，那么$Tp$的唯一分解中$p$的幂$\ge 2$，而当$p^{\prime }\ne p$时$\frac{T}{p^{\prime }}$必然包括平方因子$p^2$，此时所有的莫比乌斯函数值为$0$，只有当$p^{\prime }=p$时，$\frac{T}{p^{\prime }}$才有可能不出现平方因子，于是此时
  $$f(Tp)=\mu (T)$$

• 如果$T$不包含$p$，那么此时$Tp$的唯一分解为
  $$Tp=p_1^{a_1}{p}_2^{a_2}...p_n^{a_n}p$$

  枚举出所有的$\frac{T}{p^{\prime }}$，有
  $$\begin{gathered} p_2^{a_2}{p}_3^{a_3}...p_n^{a_n}p \\ {p}_1^{a_1}{p}_3^{a_3}...p_n^{a_n}p \\ {p}_1^{a_1}{p}_2^{a_2}...p_n^{a_n}p \\ ... \\ {p}_1^{a_1}{p}_2^{a_2}...p_n^{a_n} \end{gathered}$$
  除了最后一项都带有$p$，而莫比乌斯函数是个积性函数，所以要求除了最后一项的莫比乌斯函数值，可以求得前面的部分，再乘$\mu (p)$，比如说第一项
  $$\mu (p_2^{a_2}{p}_3^{a_3}...p_n^{a_n}p)=\mu (p_2^{a_2}{p}_3^{a_3}...p_n^{a_n})\mu (p)$$
  此时我们将除最后一项的其他项都写成这样的形式，可以提出一个$\mu (p)$，此时这些的求和就为
  $$\mu (p)[\mu (p_2^{a_2}{p}_3^{a_3}...p_n^{a_n})+\mu (p_1^{a_1}{p}_3^{a_3}...p_n^{a_n})+\mu (p_1^{a_1}{p}_2^{a_2}...p_n^{a_n})]$$
  中括号内的部分恰好就是$f(T)$，于是这部分值就为$\mu (p)f(T)$

  最后一项即$T$本身的莫比乌斯函数值，于是此时有
  $$f(Tp)=\mu (p)f(T)+\mu (T)$$

最后在数论分块的时候需要区间求和$f(T)$，给$f(T)$做一个前缀和即可$O(1)$求出

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using ll=long long;
const int N=1e7+5;

bool nt[N];
int prime[N],cnt,mu[N],f[N];

void make_prime()
{
	mu[1]=1;
	for(int i=2;i<=10000000;i++)
	{
		if(!nt[i]) prime[++cnt]=i,mu[i]=-1,f[i]=1;
		for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++)
		{
			nt[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
                mu[i*prime[j]]=0;
				f[i*prime[j]]=mu[i];
				break;
			}
			else
            {
                mu[i*prime[j]]=mu[i]*mu[prime[j]];
                f[i*prime[j]]=mu[i]+f[i]*mu[prime[j]];
            }
		}
	}
    for(int i=1;i<=10000000;i++) f[i]+=f[i-1];
}

int main()
{
	make_prime();
	int t; cin>>t;
	while(t--)
	{
		int n,m; ll ans=0; scanf("%d%d",&n,&m);
		if(n>m) swap(n,m);
		for(int l=1,r;l<=n;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			ans+=1ll*(n/l)*(m/l)*(f[r]-f[l-1]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58