「NOI 2010」能量采集

Problem

Description

给定一个 n\times m 的点阵,其中第 r 行第 c 个点的坐标为 (r,c)
(r,c) \left(0,0\right) 的连线上的点数(不包括其本身)为 v_{rc}

\sum_{r=1}^{n}\sum_{c=1}^{m}2v_{rc}-1

Constraints

1\le n,m\le 10^{5}

Solution

Analysis

易知答案即为

2\sum_{r=1}^{n}\sum_{c=1}^{m}(r,c)-nm

考虑如何求 \sum_{r=1}^{n}\sum_{c=1}^{m}(r,c) ,发现这就是 Möbius Inversion 的典型例题。

h=\min\left(n,m\right) ,则:

\begin{aligned} \sum_{r=1}^{n}\sum_{c=1}^{m}(r,c) &=\sum_{d=1}^{h}\sum_{r=1}^{n}\sum_{c=1}^{m}\left[(r,c)=d\right]\\ &=\sum_{d=1}^{h}d\sum_{r=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{c=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum_{d'=1}^{\left\lfloor\frac{h}{d}\right\rfloor}\left[d' | r\right]\left[d' | c\right]\mu(d')\\ &=\sum_{d=1}^{h}d\sum_{d'=1}^{\left\lfloor\frac{h}{d}\right\rfloor}\mu(d')\left\lfloor\frac{n}{dd'}\right\rfloor\left\lfloor\frac{m}{dd'}\right\rfloor\\ &=\sum_{D=1}^{h}\left\lfloor\frac{n}{D}\right\rfloor\left\lfloor\frac{m}{D}\right\rfloor\sum_{d | D}d\mu\left(\frac{D}{d}\right)\\ &=\sum_{D=1}^{h}\left\lfloor\frac{n}{D}\right\rfloor\left\lfloor\frac{m}{D}\right\rfloor\varphi(d) \end{aligned}

线筛出 \varphi(n) 并求和即可。

时间复杂度 O\left(\min\left(n,m\right)\sqrt{\min\left(n,m\right)}\right)

有没有更简单的做法呢?

qwq

有!

f(d) 为满足 (r,c)=d 的数对 (r,c) 的数量,发现 f(d) 并不能快速求出。
考虑使用容斥

g(d) 为满足 d | (r,c) 的数对 (r,c) 的数量,记 h=\min\left(n,m\right) ,则显然有:

g(d)=\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor

f(d)=g(d)-\sum_{i=2}^{\left\lfloor\frac{h}{d}\right\rfloor}g\left(id\right)

最终答案即为:

\sum_{d=1}^{h}\left(2d-1\right)f(d)

时间复杂度 O\left(\min\left(n,m\right)\log{\min\left(n,m\right)}\right)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>


using i64=long long;
#define Maxn 100001
template<typename T>inline T Min(const T&x,const T&y){return x<y?x:y;}

i64 F[Maxn];
int n,m;
inline i64 g(const int&d){return(i64)(n/d)*(m/d);}

int main(){
scanf(" %d %d",&n,&m);
int h=Min(n,m);
i64 Ans=0;
for(int d=h;d;--d){
i64 tmp=g(d);
for(int i=2;i*d<=h;++i)
tmp-=F[i*d];
F[d]=tmp;
Ans+=tmp*(d+d-1);
}return(printf("%lld",Ans),0);
}