P1447:[NOI2010]能量采集题解

解法

这道题是一道裸题,考察莫比乌斯反演和 Dirichlet 卷积的知识。

在这里我们规定\(n<m\),这两者调换不会对答案产生影响。然后我们来观察这个计数规律,发现每一个点对答案的贡献至少为\(1\),附加的贡献其实就是当前线段上除了本身的整点(整数坐标点)个数的两倍,换句话说就是:

\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]

化简一下就是:

\[ ans = 2 \left( \sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j) \right) – nm \]

我们可以把重点放在\( \left( \sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j) \right) \)上,可以考虑直接枚举\(gcd(i, j) = d\)然后加一个条件表达式:

\[ \sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^m d [gcd(i, j) = d] \]

考虑提出一个\(d\),并且在后面的两个和式中除掉一个\(d\):

\[ \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i, j) = 1] \]

看到经典的\(\epsilon\)函数就立马想到莫比乌斯反演(\(\mu * I = \epsilon\)),考虑带入:

\[ \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{h|i, h|j} \mu(h) \]

考虑把\( \sum_{h|i, h|j} \mu(h) \)中间的条件写成判别表达式\( [h|i][h|j] \),并把\(h\)的枚举提到前面去:

\[ \sum_{d = 1}^n d \sum_{h = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(h) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [h|i][h|j] \]

发现可以直接除掉\(h\)来化简:

\[ \sum_{d = 1}^n d \sum_{h = 1}^{\lfloor \frac{n}{hd} \rfloor} \mu(h) \sum_{i = 1}^{\lfloor \frac{n}{hd} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{hd} \rfloor} 1 \\ \sum_{d = 1}^n d \sum_{h = 1}^{\lfloor \frac{n}{hd} \rfloor} \mu(h) \lfloor \frac{n}{hd} \rfloor \lfloor \frac{m}{hd} \rfloor \]

考虑枚举\(T = hd\),注意条件的问题:

\[ \sum_{d = 1}^n d \sum_{d|T}^n \mu(\lfloor \frac{T}{d} \rfloor) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \]

考虑调换求和顺序,交换\(T\)和\(d\)的枚举:

\[ \sum_{T = 1}^n \sum_{d|T} d \mu(\lfloor \frac{T}{d} \rfloor) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \]

提取之后发现神奇性质:

\[ \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d|T} d \mu(\frac{T}{d}) \]

这不卷积么:\( \sum_{d|T} d \mu(\frac{T}{d}) \),回忆起有\(id * \mu = \varphi\)(不记得的话这里有证明),果断带入\(\varphi\):

\[ \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \varphi(T) \]

整除分块之后这道题就搞定了。

代码

// P1447.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX_N = 101000;

ll phi[MAX_N], prime[MAX_N], n, m, tot;
bool vis[MAX_N];

int main()
{
    scanf("%lld%lld", &n, &m);
    if (n > m)
        swap(n, m);
    phi[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (!vis[i])
            phi[prime[++tot] = i] = i - 1;
        for (int j = 1; j <= tot && i * prime[j] < MAX_N; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for (int i = 1; i < MAX_N; i++)
        phi[i] += phi[i - 1];
    ll ans = 0;
    for (ll T = 1, gx; T <= n; T = gx + 1)
    {
        gx = min(n / (n / T), m / (m / T));
        ans += (phi[gx] - phi[T - 1]) * (n / T) * (m / T);
    }
    ans = 2 * ans - n * m;
    printf("%lld", ans);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

《P1447:[NOI2010]能量采集题解》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注