51Nod1222 最小公倍数计数

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

首先枚举，

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

首先考虑。假如规定，我们可以通过枚举和（确保和递增，如果后面的数不管怎么填都不能满足限制就结束枚举），通过和计算可行的的个数就能在的时间内计算。（大力积分一下，或者放缩一下就能证明复杂度。）如果和不要求递增，可以在枚举的时候讨论一下有几个数重复出现了，最后乘上系数计算。

要求的式子前面还套了一层的求和。然而在后面的规模里以负二次方出现了，后面求和的规模减小得很快。大力积分告诉我们，直接枚举的复杂度就是，可以通过本题。

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