Label

灵活变换求和次序的普通莫比乌斯反演

Description

给定 T ( T = 1 0 4 ) T(T=10^4) T(T=104)组 n , m ( 1 ≤ n , m ≤ 1 0 7 ) n,m(1\leq n,m\leq 10^7) n,m(1≤n,m≤107)，求：

​ ∑ i = 1 n ∑ j = 1 m [ ( i , j ) ∈ p r i m e ] \sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)\in prime] i=1∑n​j=1∑m​[(i,j)∈prime]

Solution

∑ i = 1 n ∑ j = 1 m [ ( i , j ) ∈ p r i m e ] \sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)\in prime] i=1∑n​j=1∑m​[(i,j)∈prime]

= ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ i = 1 n ∑ j = 1 m [ ( i , j ) = p ] =\sum_{p\in prime}^{p\le min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=p] =p∈prime∑p≤min(n,m)​i=1∑n​j=1∑m​[(i,j)=p]

= ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ m p ⌋ [ ( i , j ) = 1 ] =\sum_{p\in prime}^{p\le min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[(i,j)=1] =p∈prime∑p≤min(n,m)​i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​[(i,j)=1]

= ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ m p ⌋ ∑ d ∣ ( i , j ) μ ( d ) =\sum_{p\in prime}^{p\le min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|(i,j)}\mu(d) =p∈prime∑p≤min(n,m)​i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​d∣(i,j)∑​μ(d)

= ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ d = 1 m i n ( ⌊ n p ⌋ , ⌊ m p ⌋ ) μ ( d ) ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ m p ⌋ [ d ∣ ( i , j ) ] =\sum_{p\in prime}^{p\le min(n,m)}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[d|(i,j)] =p∈prime∑p≤min(n,m)​d=1∑min(⌊pn​⌋,⌊pm​⌋)​μ(d)i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​[d∣(i,j)]

= ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ d = 1 m i n ( ⌊ n p ⌋ , ⌊ m p ⌋ ) μ ( d ) ∑ i = 1 ⌊ n p d ⌋ ∑ j = 1 ⌊ m p d ⌋ =\sum_{p\in prime}^{p\le min(n,m)}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{pd}\rfloor} =p∈prime∑p≤min(n,m)​d=1∑min(⌊pn​⌋,⌊pm​⌋)​μ(d)i=1∑⌊pdn​⌋​j=1∑⌊pdm​⌋​

= ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ d = 1 m i n ( ⌊ n p ⌋ , ⌊ m p ⌋ ) μ ( d ) ⌊ n p d ⌋ ⌊ m p d ⌋ （ 1 ） =\sum_{p\in prime}^{p\le min(n,m)}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor（1） =p∈prime∑p≤min(n,m)​d=1∑min(⌊pn​⌋,⌊pm​⌋)​μ(d)⌊pdn​⌋⌊pdm​⌋（1）

我们按照常规反演处理方法化简到这里时不难发现：后面的这个式子虽然可以数论分块处理，但此题的数据范围来讲，最前面求和符号代表的枚举素数操作的复杂度无法令人接受。此处，我们必须将素数求和号拿到式子后面去。

事实上，如果把 d d d的求和号提到最前面，后面的 ⌊ n p d ⌋ ⌊ m p d ⌋ \lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor ⌊pdn​⌋⌊pdm​⌋的计算还是无法避开枚举素数。事实上，最好的处理办法是：将原式改写为第一层求和符号枚举 p d pd pd的式子。

考虑在当前最简式 = ∑ p ∈ p r i m e p ≤ m i n ( n , m ) ∑ d = 1 m i n ( ⌊ n p ⌋ , ⌊ m p ⌋ ) μ ( d ) ⌊ n p d ⌋ ⌊ m p d ⌋ =\sum_{p\in prime}^{p\le min(n,m)}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor =p∈prime∑p≤min(n,m)​d=1∑min(⌊pn​⌋,⌊pm​⌋)​μ(d)⌊pdn​⌋⌊pdm​⌋里 p , d p,d p,d的含义：枚举素数的同时，我们又枚举所有 p p p的倍数 p d pd pd。所以，考虑当 p d = i pd=i pd=i时， p , d p,d p,d需满足什么条件才使得其对 ⌊ n i ⌋ ⌊ m i ⌋ \lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor ⌊in​⌋⌊im​⌋有贡献，我们可以直接将（1）式变换成如下式子：

​ ∑ i = 1 n ⌊ n i ⌋ ⌊ m i ⌋ ∑ p ∈ p r i m e , p ∣ i p ≤ i μ ( ⌊ i p ⌋ ) （ 2 ） \sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor\sum_{p\in prime,p|i}^{p\leq i}\mu(\lfloor\frac{i}{p}\rfloor)（2） i=1∑n​⌊in​⌋⌊im​⌋p∈prime,p∣i∑p≤i​μ(⌊pi​⌋)（2）

（其实上述式子 p d ( = i ) pd(=i) pd(=i)下界应为2，但 p d = 1 pd=1 pd=1时对应的项值为0，对答案无影响。事实上，（从某篇文章中看到的）我们通过变换求和次序的好处之一就在于：大大省略了对答案无影响的0项的枚举计算。）

对于 ∑ p ∈ p r i m e , p ∣ i p ≤ i μ ( ⌊ i p ⌋ ) \sum_{p\in prime,p|i}^{p\leq i}\mu(\lfloor\frac{i}{p}\rfloor) ∑p∈prime,p∣ip≤i​μ(⌊pi​⌋)，在 O ( n ) O(n) O(n)预处理出 μ ( 1 ) ∼ μ ( n ) \mu(1)\sim \mu(n) μ(1)∼μ(n)的值后，可利用未经优化的埃氏筛预处理。之后便可对（2）式进行数论分块。

算法时间复杂度： O ( n l o g l o g n ) O(nloglogn) O(nloglogn)（瓶颈在于埃氏筛）。

Code

#include<cstdio>
#include<iostream>
#define ri register int
#define ll long long
using namespace std;

const int MAXN=1e7+20;
int T,N,M,prime[MAXN],cnt,mu[MAXN];
ll sum[MAXN],ans;
bool notprime[MAXN];

void Eulasieve()
{
	mu[1]=1,notprime[1]=true;
	for(ri i=2;i<=MAXN;++i)
	{
		if(!notprime[i]) prime[++cnt]=i,mu[i]=-1;
		for(ri j=1;j<=cnt&&i*prime[j]<=MAXN;++j)
		{
			notprime[i*prime[j]]=true;
			if(i%prime[j]==0) break;
			else mu[i*prime[j]]=-mu[i];
		}
	}
}

void Estsieve()
{
	sum[1]=0;
	for(ri i=2;i<=MAXN;++i)
		if(!notprime[i])
			for(ri j=1;i*j<=MAXN;++j) sum[i*j]+=(ll)mu[j];
	for(ri i=1;i<=MAXN;++i) sum[i]=sum[i-1]+sum[i];
}

int main()
{
	std::ios::sync_with_stdio(false);
	Eulasieve(),Estsieve();
	cin>>T;
	for(ri op=1;op<=T;++op)
	{
		cin>>N>>M;
		if(N>M) swap(N,M);
		ans=0LL;
		for(ri l=2,r;l<=N;l=r+1)
		{
			r=min(N/(N/l),M/(M/l));
			ans+=(ll)(N/l)*(ll)(M/l)*(sum[r]-sum[l-1]);
		}
		cout<<ans<<'\n';
	}
	return 0;
}