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

2019-01-04 09:51:39


在蒟蒻的博客里查看

据大佬们说,这题就是求$(\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)

#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;
}