ACM模版

描述

题解

先来分析题，设 f(n)=∑ni=1μ(i) ，那么 ans=f(b)−f(a−1) 。

接下来我们来说莫比乌斯函数，在《具体数学》中对莫比乌斯的性质讲述的十分详细，其中有一个是

∑d|nμ(d)=[n=1]

所以呢，对于我们所需要求的 f(n) 来说，需要进行如下推导：

∑i=1n∑d|iμ(d)=1
∑d=1n∑i=1ndμ(i)=1
∑d=1nf(nd)=1
∑d=2nf(nd)+f(n)=1
所以，我们也就获取了最后的公式为：
f(n)=1−∑d=2nf(nd)

推导到这里都还好理解，但是直接这样搞肯定会超时的，因为数据略萌，也想不出来怎么搞，于是找了一发题解，找到了 alan_cty’s blog 的题解及代码，说到需要用到分块儿来加速，并且用上记忆化搞搞，另外需要先预处理出来一部分前缀和来进一步加速，额，有些懵逼，因为对他的 cal() 函数不甚理解，里面的思想不是特别清楚……好吃力看着，想了半天也没有想通为什么这样子搞，暂时先 mark 一下把，如果哪个大佬能够答疑解惑，将不胜感激~~~

代码

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXN = 5e6 + 10;
const int MOD = 857777;

ll a, b;
int tot;
ll tmp[MOD];
ll val[MOD];
int mu[MAXN];
int prime[MAXN];
int sum[MAXN];
int nxt[MOD];
int had[MOD];
bool vis[MAXN];

void add(int x, ll y, int z)
{
    val[++tot] = y;
    nxt[tot] = had[x];
    had[x] = tot;
    tmp[tot] = z;
}

ll cal(ll x)
{
    int t = x % MOD, ret = 1;
    if (x <= MAXN)
    {
        return sum[x];
    }
    for (int i = had[t]; i; i = nxt[i])
    {
        if (val[i] == x)
        {
            return tmp[i];
        }
    }

    ll l = 2, r;
    while (l <= x)
    {
        r = x / (x / l);
        ret -= 1ll * (r - l + 1) * cal(x / l);
        l = r + 1;
    }
    add(t, x, ret);
    return ret;
}

void init()
{
    tot = 0;

    // 线性筛法求解部分莫比乌斯函数
    mu[1] = 1;
    for (int i = 2; i <= MAXN; i++)
    {
        if (!vis[i])
        {
            mu[i] = -1;
            prime[++prime[0]] = i;
        }
        for (int j = 1, t; j <= prime[0]; j++)
        {
            t = i * prime[j];
            if (t > MAXN)
            {
                break;
            }
            vis[t] = 1;
            if (!(i % prime[j]))
            {
                break;
            }
            mu[t] = -mu[i];
        }
    }

    for (int i = 1; i <= MAXN; i++)
    {
        sum[i] = sum[i - 1] + mu[i];
    }
}

int main()
{
    init();

    scanf("%lld%lld", &a, &b);
    printf("%lld", cal(b) - cal(a - 1));

    return 0;
}