BZOJ2820 YY的GCD

发表于 | 更新于

Link

Solution

定义F(x)F(x)为x∣gcd(a,b)x|gcd(a,b)的对数 f(x)f(x)为gcd(a,b)==xgcd(a,b)==x的对数 则

F(x)=[nx][mx]=∑x∣df(d)F(x)=[\dfrac nx][\dfrac mx]=\sum_{x|d}f(d)f(x)=∑x∣dμ(dx)F(d)=∑x∣dμ(dx)[nd][md]f(x)=\sum_{x|d}\mu(\dfrac dx)F(d)=\sum_{x|d}\mu(\dfrac dx)[\dfrac nd][\dfrac md]

按照套路，一般把xx提出来可以简化问题 于是

f(1)=∑1∣dμ(d)F(d)=∑1∣dμ(d)[nxd][mxd]f(1)=\sum_{1|d}\mu(d)F(d)=\sum_{1|d}\mu(d)[\dfrac n{xd}][\dfrac m{xd}]

要求的是

∑p∈Pf(p)=∑p∈P∑1∣dμ(d)F(d)\sum_{p\in P}f(p)=\sum_{p\in P}\sum_{1|d}\mu(d)F(d)=∑p∈P∑1∣dμ(d)[npd][mpd]=\sum_{p\in P}\sum_{1|d}\mu(d)[\dfrac n{pd}][\dfrac m{pd}]

数据规模决定不能分别枚举一遍p,dp,d。看到这个式子长得比较可爱，令T=pdT=pd，则问题变成了

∑T(∑p∣Tμ(Tp)[nT][mT])\sum_T(\sum_{p|T}\mu(\dfrac Tp)[\dfrac nT][\dfrac mT])

于是，看到了熟悉的可以分块加速的项，思考能不能把

∑p∣Tμ(Tp)\sum_{p|T}\mu(\dfrac Tp)

弄出个前缀和。然后这是可以暴力求的。

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int N=10000000,MAXN=N+10;
typedef long long LL;
using std::swap;
using std::min;

LL Sum[MAXN];
int mu[MAXN],prime[MAXN],pcnt;
void Shake()
{
	static bool notp[MAXN];
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
		{
			prime[++pcnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=pcnt && prime[j]*i<=N;j++)
		{
			notp[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else
				mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=pcnt;i++)
		for(int p=prime[i];p<=N;p+=prime[i])
			Sum[p]+=mu[p/prime[i]];
	for(int i=1;i<=N;i++)
		Sum[i]+=Sum[i-1];
}
LL Calc(int n,int m)
{
	LL res=0;
	if(n>m) swap(n,m);
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		res+=(Sum[r]-Sum[l-1])*(n/l)*(m/l);
	}
	return res;
}
int main()
{
	freopen("input","r",stdin);
	Shake();
	int T;red(T);
	while(T--)
	{
		int n,m;red(n),red(m);
		printf("%lld\n",Calc(n,m));
	}
	return 0;
}