OI题解 - 能量采集[BZOJ 2005]

终于完全看懂一次题解……
然后自己按照理解再写一发~


· 题意 #传送门#

(Tab. 原题目经分析得到……)

给出 $n,m$ ,求 $\sum_{i=1}^n\sum_{j=1}^m2\gcd(i,j)-1$ 。


· 解析

因为 $m,n$ 比较大,不难想到用数论解决。又因为 gcd 与莫比乌斯反演有密不可分的联系,所以从这个角度想可能会 easy 一些~

推导的过程如下:

不妨假设 $n<m$ ;

先把求和里的式子化简一下:

$ $令 $g=\gcd(i,j)$,那么我们就要求 “$\sum_{i=1}^n\sum_{j=1}^mg$”;

根据反演的结论 “$n=\sum_{d|n}\phi(n)$” ,我们把它代入式子,可得:

按照套路把枚举 $d$ 的求和拿到外面来:

不难由 $i\in[1,n]$ , $j\in[1,m]$ 想到满足 $d|i$ 的 $i$ 的取值有 $\left\lfloor\frac{n}{d}\right\rfloor$ 个,满足 $d|j$ 的 $j$ 的取值有 $\left\lfloor\frac{m}{d}\right\rfloor$ 个;则:

现在预处理出 $\phi()$ (线性筛),然后枚举就可以了~


· 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int SIZ=1e5;
int r,c;
ll ans;
ll phi[SIZ+4],prm[SIZ+4];
bool vis[SIZ+4];
void SelectPhi(){
phi[1]=1;
for(ll i=2;i<=SIZ;i++){
if(!vis[i]){
prm[++prm[0]]=i;
phi[i]=i-1;
}
for(int j=1;j<=prm[0] && prm[j]*i<=SIZ;j++){
vis[prm[j]*i]=true;
if(i%prm[j]==0){
phi[i*prm[j]]=phi[i]*prm[j];
break;
}
else phi[i*prm[j]]=phi[i]*phi[prm[j]];
}
}
}
int main(){
scanf("%d%d",&r,&c);
SelectPhi();
ll ans=0;
for(int i=min(r,c);i;i--)
ans+=1ll*(r/i)*(c/i)*phi[i];
printf("%lld\n",2*ans-1ll*r*c);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%