51nod 1244 莫比乌斯函数之和(杜教筛)

Description:

莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下：

如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。

如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n) = (-1)^k。例如：miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。

给出一个区间[a,b]，S(a,b) = miu(a) + miu(a + 1) + … miu(b)。

例如：S(3, 10) = miu(3) + miu(4) + miu(5) + miu(6) + miu(7) + miu(8) + miu(9) + miu(10)

= -1 + 0 + -1 + 1 + -1 + 0 + 0 + 1 = -1。

Input:

输入包括两个数a, b，中间用空格分隔(2 <= a <= b <= 10^10)

Output

输出S(a, b)。

Sample Input:

3 10

Sample Output:

-1

题目链接

此题为求出区间 $[a,b]$[a,b] 之间的莫比乌斯函数之和，显然 ${\sum }_{i=a}^b\mu \left(i\right)={\sum }_{i=1}^b\mu \left(i\right)-{\sum }_{i=1}^a\mu \left(i\right)$i=a∑b​μ(i)=i=1∑b​μ(i)−i=1∑a​μ(i) ，所以我们只需对 $n$n 求出 ${\sum }_{i=1}^n\mu \left(i\right)$i=1∑n​μ(i) 即可

而莫比乌斯函数 $\mu$μ 我们已知为积性函数，求积性函数的前缀和那么显然就用杜教筛来求啦

杜教筛的学习可以参考

唐老师(skywalkert)的博客 浅谈一类积性函数的前缀和

吉老师(jiry_2)的博客 论逗逼的自我修养之寒假颓废记

任之洲的论文 积性函数求和的几种方法 (2016 年信息学奥林匹克中国国家队候选队员论文集)

杜教筛用于在低于线性的时间复杂度内求出一些积性函数的前缀和

现在我们需要求出积性函数 $\mu$μ 的前缀和，考虑莫比乌斯函数的性质 $\mu \ast I=ϵ$μ∗I=ϵ （ $\ast$∗ 为狄利克雷卷积）

根据杜教筛的核心式就有

$\sum _{i=1}^n\mu \left(i\right)=\sum _{i=1}^n\left(\mu \right(i)\ast I(i\left)\right)-\sum _{i=2}^{n}I\left(i\right)\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }\mu \left(j\right)=\sum _{i=1}^nϵ\left(i\right)-\sum _{i=2}^{n}I\left(i\right)\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }\mu \left(j\right)$i=1∑n​μ(i)=i=1∑n​(μ(i)∗I(i))−i=2∑n​I(i)j=1∑⌊in​⌋​μ(j)=i=1∑n​ϵ(i)−i=2∑n​I(i)j=1∑⌊in​⌋​μ(j)

显然其中 $ϵ$ϵ 与 $I$I 的前缀和很好求，再用整除分块和记忆化搜索优化一下就可以了

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 5e6 + 5;

bool IsPrime[maxn];
int Tot;
int Prime[maxn];
int Mu[maxn];
ll PrefixMu[maxn];

void Sieve() {
    for (int i = 2; i < maxn; ++i) IsPrime[i] = true;
    Mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (IsPrime[i]) {
            Prime[Tot++] = i;
            Mu[i] = -1;
        }
        for (int j = 0; j < Tot && i * Prime[j] < maxn; ++j) {
            IsPrime[i * Prime[j]] = false;
            if (i % Prime[j] == 0) {
                Mu[i % Prime[j]] = 0;
                break;
            }
            Mu[i * Prime[j]] = -Mu[i];
        }
    }
    for (int i = 1; i < maxn; ++i) PrefixMu[i] = PrefixMu[i - 1] + Mu[i];
}

map<ll, ll> SumMu;

ll SigmaMu(ll Key) {
    if (Key < maxn) return PrefixMu[Key];
    if (SumMu[Key]) return SumMu[Key];
    ll Ans = 1;
    for (ll l = 2, tp; l <= Key; l = tp + 1) {
        tp = Key / (Key / l);
        Ans -= (tp - l + 1) * SigmaMu(Key / l);
    }
    SumMu[Key] = Ans;
    return SumMu[Key];
}

ll A, B;

int main(int argc, char *argv[]) {
    Sieve();
    scanf("%lld%lld", &A, &B);
    printf("%lld\n", SigmaMu(B) - SigmaMu(A- 1));
    return 0;
}