题解 P1447 【[NOI2010]能量采集】
interestingLSY
2018-08-13 23:22:59
# ① 抽象为模型:
就是给你一个$n\cdot m$的方阵,问每个点与原点的连线中有多少点(不包括两头的)*2+1再求和,
形式化地说,就是求
$$\color{blue}\sum_{i=1}^{n}\sum_{j=1}^{m}gcd_{i,j}\cdot2-1$$
注意是减,因为我们不计算这条线段两端点
即为
$$\color{blue}\left[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd_{i,j}\right]\color{black}\cdot2\ -\ nm$$
好现在的~~主要矛盾~~就是求蓝色那部分.
# ② 开始乱搞
正向不好求,我们考虑~~暴力(顺便说一句,这题暴力求上面式子有$\color{green}80$分qwq)~~反着求,即
开一个$cnt$数组, $cnt_i$表示**公约数**为i的**数对**个数.(注意不是最大公因数)
~~显然~~根据乘法原理,
$$\color{Blue}cnt_i = \left\lfloor\frac{n}{i}\right\rfloor+\left\lfloor\frac{m}{i}\right\rfloor$$
但是我们忽略了一点,就是一个数对可以产生公因数$x$,也**可能**产生公因数$2x,3x......$
所以咋整?减掉就行!
# Code:
注意一点:最终减掉$nm$时要减去`1LL*n*m`,不然会爆
(只贴出关键部分)
```cpp
Read(n,m);
For(i,max(n,m))
cnt[i] = 1LL * (n/i) * (m/i);
fOR(i,max(n,m)){
int x = i+i;
g[i] = cnt[i];
while( x <= max(n,m) ){
g[i] -= g[x];
x += i;
}
}
For(i,max(n,m))
ans += 1LL * i * g[i];
printf("%lld",ans*2LL-1LL*n*m);
```