<题解>[SDOI2015]约数个数和

洛谷的题目链接

\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)(没问题\sigma_0也记作d,我更喜欢前者)

前置结论

一个结论:\sigma_0(xy) = \sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i, j)=1]
感性证明一下:

我们考虑对xy的所有约数进行映射。考虑xy的一个约数可以分解成为\prod p_i^{c_i},而x=k_1p_i^{a_i},y=k_2p_i^{b_i}。我们约定:

  1. a_i\ge c_i,那么p_i全部来自x
  2. a_i,那么p_i^{c_i}=p_i^{a_i}p_i^{d_i}p_i^{d_i}来自y

这样我们就可以将xy的约数与这种划分方式建立双射的关系了。如果我们取i|x,j|y,那么如果\gcd(i,j)=1,那么因为我们规定了只有把x里面的p_i拿完了才能拿y里面的p_i,所以选择了y里面的p_i就代表一定要选择完x里面的p_i这是y的义务

莫比乌斯反演

有了这个结论,这题就非常好做了。

\begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)\quad(n\le m)\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{x|i}\sum_{y|j}[x|i][y|j][\gcd(x, y)=1]\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{x=1}^n\sum_{y=1}^m[x|i][y|j]\sum_{d|\gcd(x,y)}\mu(d)\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{x=1}^n\sum_{y=1}^m[x|i][y|j]\sum_{d=1}^n\mu(d)[d|\gcd(x, y)]\\ =&\sum_{d=1}^n\mu(d)\sum_{x=1}^n\sum_{y=1}^m[d|\gcd(x, y)] (\sum_{i=1}^n[x|i])(\sum_{j=1}^m[y|j])\\ =&\sum_{d=1}^n\mu(d)\sum_{x=1}^n\sum_{y=1}^m[d|\gcd(x, y)] \lfloor\dfrac n x\rfloor\lfloor \dfrac m y\rfloor\\ =&\sum_{d=1}^n\mu(d)\sum_{x=1}^n\sum_{y=1}^m[d|x][d|y] \lfloor\dfrac n x\rfloor\lfloor \dfrac m y\rfloor\\ =&\sum_{d=1}^n\mu(d)\sum_{x=1}^n\sum_{y=1}^m[d|x][d|y] \lfloor\dfrac n x\rfloor\lfloor \dfrac m y\rfloor\\ =&\sum_{d=1}^n\mu(n)\sum_{x=1}^{\lfloor\frac n d\rfloor}\sum_{y=1}^{\lfloor\frac m d\rfloor}\lfloor\dfrac n {dx}\rfloor\lfloor\dfrac m {dy}\rfloor\\ &【枚举了d的倍数】 =&\sum_{d=1}^n\mu(n)\Big(\sum_{x=1}^{\lfloor\frac n d\rfloor}\lfloor\dfrac n {dx}\rfloor\Big)\Big(\sum_{y=1}^{\lfloor\frac m d\rfloor}\lfloor\dfrac m {dy}\rfloor\Big) \end{aligned}

f(x) = \sum\limits_{i=1}^x\lfloor\dfrac x i\rfloor,则原式=\sum\limits_{d=1}^n\mu(n)f(\lfloor\frac n d\rfloor)f(\lfloor\frac m d\rfloor),预处理\mu,整除分块,记忆化f即可。f总耗时N\sqrt N,每个询问耗时\sqrt N,预计耗时O(N\sqrt N)

#include <cstdio>
#include <algorithm>

using std::min;
using std::swap;

const int N = 50000 + 10;

bool np[N];
int ps[N], mu[N];

inline void calc_mu(void)
{
    mu[1] = 1;
    np[1] = true;
    for (int i = 2; i != N; ++i)
    {
        if (!np[i])
        {
            ps[++ps[0]] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= ps[0] && i * ps[j] < N; ++j)
        {
            np[i * ps[j]] = true;
            if (i % ps[j] == 0)
            {
                mu[i * ps[j]] = 0;
                break;
            }
            mu[i * ps[j]] = -mu[i];
        }
    }
}

long long F[N];

long long f(int n)
{
    if (F[n])
        return F[n];
    long long ret = 0;
    for (int i = 1, j; i <= n; i = j + 1)
    {
        j = n / (n / i);
        ret += (long long)(j - i + 1) * (n / i);
    }
    return F[n] = ret;
}

int main(void)
{
    calc_mu();
    for (int i = 1; i != N; ++i)
        mu[i] += mu[i - 1];
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        if (n > m)
            swap(n, m);
        long long ans = 0;
        for (int i = 1, j; i <= n; i = j + 1)
        {
            j = std::min(n / (n / i), m / (m / i));
            ans += f(n / i) * f(m / i) * (mu[j] - mu[i - 1]);
        }
        printf("%lld\n", ans);
    }
}
点赞

发表评论

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