题解 P1447 【[NOI2010]能量采集】

吹雪吹雪吹

2019-01-04 09:51:39

Solution

[在蒟蒻的博客里查看](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; } ```