bzoj 4018 小Q的幻想之乡

Posted on | Edited on | Views:

莫比乌斯反演 + 线性筛.

由于每次只能走一种路径,并且边是双向的,所以从 $i$ 到 $j$ 的边数就是 $\frac {|i-j|} {\gcd(i,j)}$ .

于是每次询问要求 $ans=\sum_{i=1}^n \sum_{j=1}^m \frac {|i-j|} {\gcd(i,j)}$ .

与 $\gcd$ 有关的式子,考虑用莫比乌斯反演那一套操作,假定 $n\le m$ ,开始推式子,

记 $A=\min(\lfloor \frac n d\rfloor,\lfloor \frac m d\rfloor),B=\max(\lfloor \frac n d\rfloor,\lfloor \frac m d\rfloor)$ .

则后面那个 $\sum_{i=1}^A \sum_{j=1}^B |i-j|=\frac {(A-1)A(A+1)} 3+\frac {AB(B-A)} 2$ ,大佬的推导过程 .

前面那一块,需要预处理 $f(d)=\sum_{k|d} k\cdot \mu(k)$ 的前缀和,这是个积性函数,直接线性筛处理.

然后整除分块计算答案,时间复杂度 $O(n+T\cdot \sqrt m)$ .

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P1=1e9+7,P2=1e9+9;
struct Z
{
	int v1,v2;
	Z(int v1=0,int v2=0):v1(v1),v2(v2) {}
	Z operator + (const Z &rhs) const
	{
		return Z(v1+rhs.v1>=P1?v1+rhs.v1-P1:v1+rhs.v1,v2+rhs.v2>=P2?v2+rhs.v2-P2:v2+rhs.v2);
	}
	Z operator - (const Z &rhs) const
	{
		return Z(v1-rhs.v1<0?v1-rhs.v1+P1:v1-rhs.v1,v2-rhs.v2<0?v2-rhs.v2+P2:v2-rhs.v2);
	}
	Z operator * (const Z &rhs) const
	{
		return Z(1LL*v1*rhs.v1%P1,1LL*v2*rhs.v2%P2);
	}
	void pr()
	{
		printf("%d %d\n",v1,v2);
	}
};
Z fpow(Z a,int b)
{
	Z res=Z(1,1);
	while(b)
	{
		if(b&1)
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
const int N=2e6;
int prime[N+10],ism[N+10],pcnt=0;
Z f[N+10],inv2,inv3;
void init()
{
	inv2=fpow(Z(2,2),P1-2)*Z(1,2)*Z(1,2);
	inv3=fpow(Z(3,3),P1-2)*Z(1,3)*Z(1,3);
	f[1]=Z(1,1);
	ism[1]=1;
	for(int i=2;i<=N;++i)
	{
		if(!ism[i])
		{
			prime[++pcnt]=i;
			f[i]=Z(1,1)-Z(i,i);
		}
		for(int j=1;j<=pcnt && 1LL*i*prime[j]<=N;++j)
		{
			int num=i*prime[j];
			ism[num]=1;
			if(i%prime[j]==0)
			{
				f[num]=f[i];
				break;
			}
			f[num]=f[i]*f[prime[j]];
		}
	}
	for(int i=1;i<=N;++i)
		f[i]=f[i-1]+f[i];
}
Z calc(int a,int b)
{
	if(a>b)
		swap(a,b);
	Z A=Z(a,a),B=Z(b,b);
	Z I=Z(1,1);
	return (A-I)*A*(A+I)*inv3+A*B*(B-A)*inv2;
}
void solve()
{
	int n=read(),m=read();
	if(n>m)
		swap(n,m);
	Z ans=Z(0,0);
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		ans=ans+(f[r]-f[l-1])*calc(n/l,m/l);
	}
	ans.pr();
}
int main()
{
	init();
	int T=read();
	while(T--)
		solve();
	return 0;
}