「Luogu2257」YY的GCD

蒟蒻的第一道莫反

跟着题解推的式子，但还是记录一下过程吧

本文可能在一定程度上存在谬误，请谨慎分析

若发现文中有错误，如您愿意，恳请您向我指出，不胜感激

problem

Solution

题目要求：

ans=∑i=1N∑j=1M[gcd(i,j)∈prime]ans=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)\in prime]

令f(p)=∑i=1N∑j=1M[gcd(i,j)=p](p∈prime)f(p)=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=p](p\in prime)

再令g(p)=∑i=1N∑j=1M[p∣gcd(i,j)](p∈prime)g(p)=\sum_{i=1}^N\sum_{j=1}^M[p|gcd(i,j)](p\in prime)

于是有

g(n)=∑n∣df(d)g(n)=\sum_{n|d}f(d)

反演后可得

f(n)=∑n∣dμ(dn)g(d)f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)

又知g(d)=⌊Nd⌋⌊Md⌋g(d)=\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor

于是有

ans=∑n∈primef(n)=∑n∈prime∑n∣dμ(dn)⌊Nd⌋⌊Md⌋=∑n∣d⌊Nd⌋⌊Md⌋∑n∈primeμ(dn)=∑d=1min(N,M)⌊Nd⌋⌊Md⌋∑n∣d,n∈primeμ(dn)ans=\sum_{n\in prime}f(n)=\sum_{n\in prime}\sum_{n|d}\mu (\frac{d}{n})\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor\\=\sum_{n|d}\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor\sum_{n\in prime}\mu(\frac{d}{n})\\=\sum_{d=1}^{min(N,M)}\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor\sum_{n|d,n\in prime}\mu(\frac{d}{n})

令sum(d)=∑n∣d,n∈primeμ(dn)sum(d)=\sum_{n|d,n\in prime}\mu(\frac{d}{n})，预处理sum(d)sum(d)

那么答案即

ans=∑d=1min(M,N)⌊Nd⌋⌊Md⌋sum(d)ans=\sum_{d=1}^{min(M,N)}\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor sum(d)

∑sum(d)\sum sum(d)仍可以利用前缀和优化，∑⌊Nd⌋⌊Md⌋\sum\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor利用整除分块优化，最终时间复杂度为O(Tmin(N,M)+k)O(T\sqrt{min(N,M)}+k)，kk为预处理复杂度

Code

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
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 10000005
#define N 10000000
using namespace std;
typedef long long ll;

template <typename T> void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

int T;
int n,m;
int pri[maxn],pcnt,nop[maxn];
int mu[maxn];
ll sum[maxn],up;

void GetPrime()
{
	nop[1]=1,mu[1]=1;
	for(register int i=2;i<=N;++i)
	{
		if(!nop[i])pri[++pcnt]=i,mu[i]=-1; 
		for(register int j=1;j<=pcnt && i*pri[j]<=N;++j)
		{
			nop[i*pri[j]]=1;
			if(i%pri[j]==0)break;
			else mu[i*pri[j]]=-mu[i];
		}
	}
	for(register int i=1;i<=pcnt;++i)
		for(register int j=1;pri[i]*j<=N;++j)
			sum[pri[i]*j]+=mu[j];
	for(register int i=1;i<=N;++i)
		sum[i]+=sum[i-1];
}

ll Calc()
{
	ll re=0;
	for(register int l=1,r;l<=up;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		re+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
	}
	return re;
}

int main()
{
	read(T);
	GetPrime();
	while(T--)
	{
		read(n),read(m);
		up=min(n,m);
		printf("%lld\n",Calc());
	}
	return 0;
}