题解 P1447 【[NOI2010]能量采集】
吹雪吹雪吹
2019-01-04 09:51:39
[在蒟蒻的博客里查看](https://xcfubuki.cn/2019/Mengbiwusi/)
据大佬们说,这题就是求$(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}gcd(i, j))*2-n*m$
那么只要求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}gcd(i, j)$ 就好了0v0
#### $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}gcd(i, j)$
枚举$gcd$:
#### $\sum\limits_{k=1}^{n}k*\sum\limits_{i=1}^{n}\sum\limits_{J=1}^{m}[gcd(i,j)=k]$
老套路拎出$k$:
#### $\sum\limits_{k=1}^{n}k*\sum\limits_{i=1}^{\lfloor n/k\rfloor}\sum\limits_{J=1}^{\lfloor m/k\rfloor}[gcd(i,j)=1]$
$gcd$ 改成 $\mu$:
#### $\sum\limits_{k=1}^{n}k*\sum\limits_{i=1}^{\lfloor n/k\rfloor}\sum\limits_{j=1}^{\lfloor m/k\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)$
把$d$ 拎到外面
#### $\sum\limits_{k=1}^{n}k*\sum\limits_{d=1}^{\lfloor n/k\rfloor}\lfloor \frac{n}{kd}\rfloor \lfloor \frac{m}{kd}\rfloor*\mu(d)$
最后把 $\mu$ 筛出来,再用这个式子弄一下就好了
可以证明其时间复杂度为O(n log n)
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100005
using namespace std;
int n, m, mu[maxn], p[maxn], cnt;
long long ans = 0;
bool vis[maxn];
void Init()
{
vis[1] = 1, mu[1] = 1;
for (int i = 2; i < maxn; ++i)
{
if (!vis[i])
p[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && p[j] * i < maxn; ++j)
{
int x = i * p[j];
vis[x] = 1, mu[x] = -mu[i];
if (i % p[j] == 0)
{
mu[x] = 0;
break;
}
}
}
}
int main()
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
Init();
n = read(), m = read();
if (n > m)
swap(n, m);
for (int k = 1; k <= n; ++k)
{
int lim = n / k, res = 0;
for (int d = 1; d <= lim; ++d)
res += (n / (k * d)) * (m / (k * d)) * mu[d];
ans += 1ll * res * k;
}
ans = ans * 2 - n * m;
printf("%lld\n", ans);
return 0;
}
```