[神仙数论题] 51Nod1222 最小公倍数计数

51Nod1222 最小公倍数计数

区间的限制不好处理,首先转化成求前缀的答案。要求第一个数小于等于第二个也比较麻烦,可以先扔掉这个限制,最后可以比较方便地转化回来:

\sum\limits_{a=1}^n \sum\limits_{b=1}^n\left[lcm(a, b)\leq n\right]

首先枚举gcd

lcm(a, b) = \frac{ab}{gcd(a, b)}

=\sum\limits_{k \in N^+}\sum\limits_{a \in N^+}\sum\limits_{b \in N^+}\left[abk \leq n\right]\left[gcd(a, b) = 1\right]

然后按照套路莫比乌斯反演:

=\sum\limits_{k \in N^+}\sum\limits_{a \in N^+}\sum\limits_{b \in N^+}\left[abk \leq n\right]\sum\limits_{d|gcd(a, b)}\mu(d)

=\sum\limits_{d^2 \leq n}\mu(d)\sum\limits_{k \in N^+}\sum\limits_{a \in N^+}\sum\limits_{b \in N^+}\left[abk \leq \frac{n}{d^2}\right]

首先考虑\sum\limits_{a \in N^+}\sum\limits_{b \in N^+}\sum\limits_{c \in N^+}\left[abc \leq n\right]。假如规定a \leq b \leq c,我们可以通过枚举ab(确保a, bc递增,如果后面的数不管怎么填都不能满足限制就结束枚举),通过ab计算可行的c的个数就能在O(n^{\frac{2}{3}})的时间内计算。(大力积分一下,或者放缩一下就能证明复杂度。)如果a, bc不要求递增,可以在枚举的时候讨论一下有几个数重复出现了,最后乘上系数计算。

要求的式子前面还套了一层d的求和。然而d在后面的规模里以负二次方出现了,后面求和的规模减小得很快。大力积分\int_{1}^{\sqrt{n}}(\frac{n}{x^2})^{\frac{2}{3}}dx = O(n^{\frac{2}{3}})告诉我们,直接枚举d的复杂度就是O(n^{\frac{2}{3}}),可以通过本题。

#include <bits/stdc++.h>

typedef long long ll;

const int SIZE = 1e6;
int fac[SIZE + 1], prime[SIZE + 1], prime_n, mu[SIZE + 1];

void init()
{
    mu[1] = 1;
    for (int i = 2; i <= SIZE; i++)
    {
        if (!fac[i]) fac[i] = prime[++prime_n] = i;
        for (int j = 1; j <= prime_n && prime[j] * i <= SIZE && prime[j] <= fac[i]; j++)
            fac[prime[j] * i] = prime[j];
        mu[i] = fac[i] == fac[i / fac[i]] ? 0 : -mu[i / fac[i]];
    }
}

ll F(ll n)
{
    ll c1 = 0, c2 = 0, c3 = 0;
    for (ll i = 1; i * i * i <= n; i++)
        for (ll j = i; i * j * j <= n; j++)
        {
            if (j == i)
            {
                c1++;
                c2 += n / (i * j) - j;
            }
            else
            {
                c2++;
                c3 += n / (i * j) - j;
            }
        }
    return c1 + c2 * 3 + c3 * 6;
}

ll solve(ll n)
{
    ll ans = 0;
    for (ll i = 1; i * i <= n; i++)
        ans += mu[i] * F(n / (i * i));
    return (ans + n) / 2;
}

int main()
{
    init();
    ll a, b; scanf("%lld%lld", &a, &b);
    printf("%lld\n", solve(b) - solve(a - 1));
}


发表评论

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