bzoj 5478 gcd

Posted on | Views:

莫比乌斯反演.

  • 题面有误, $a$ 应该是 $1\sim n$ 的一个排列.因为这个卡了好久…
  • 用 $\varphi$ 反演就很好做.

  • $O(n)$ 大力枚举 $d$ ,因为 $a$ 是个排列,所以可以大力枚举集合中的每个数的约数,对 $1\sim n$ 中每个数记录一下有 $f(i)$ 个数是它的倍数,那么后面那坨就是 $\sum f(i)^2$ 了.
  • 集合大小总和是个调和级数,总时间复杂度应该是 $O(nlog^3n)$ .(其实我不会证)

直接 $memset$ 会 $T$ ,可能需要一点卡常的奇技淫巧.

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
#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 P=1e9+7;
const int MAXN=1e5+10;
inline int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int n,a[MAXN];
int phi[MAXN],ism[MAXN],cnt=0,prime[MAXN];
vector<int> factor[MAXN];
void init()
{
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;j+=i)
			factor[j].push_back(i);
	ism[1]=1,phi[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!ism[i])
			prime[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt && i*prime[j]<=n;++j)
		{
			ism[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=mul(phi[i],prime[j]);
				break;
			}
			phi[i*prime[j]]=mul(phi[i],prime[j]-1);
		}
	}
}
int f[MAXN],vis[MAXN];
int main()
{
	n=read();
	init();
	for(int i=1;i<=n;++i)
		a[i]=read();
	int ans=0;
	for(int i=1;i<=n;++i)
	{
		int res=0;
		for(int j=i;j<=n;j+=i)
		{
			int p=a[j];
			int siz=factor[p].size();
			for(int k=0;k<siz;++k)
			{
				int q=factor[p][k];
				if(vis[q]!=i)
				{
					f[q]=1;
					vis[q]=i;
				}
				else
					++f[q];
				res=add(res,mul(2*f[q]-1,phi[q]));
			}
		}
		res=mul(res,phi[i]);
		ans=add(ans,res);
	}
	cout<<ans<<endl;
	return 0;
}