51NOD 1244 莫比乌斯函数之和-白红宇

51NOD 1244 莫比乌斯函数之和

阅读量：5243 次

发布时间：2019-06-14

本文共 2799 字，大约阅读时间需要 9 分钟。

题意：

输入两个整数$a,b(2 \leq a \leq b \leq 10^{10})$

求莫比乌斯函数$\mu (n)$在区间$[a,b]$之和，即$\sum\limits_{i=a}^{b} \mu(i)$

分析：

一个引理：$n > 1$时，有$\sum\limits_{d|n} \mu(d) = 0$成立。

证明：

我们将$n$分解为$n=\prod\limits_{i=1}^{k} p_{i}^{e_{i}}$，$n$一共有$k$个不同的素因子。
只考虑$n$的不含平方数的因子$d=\prod\limits_{i=1}^{r} p_{i}^{e_{i}}$，它含有$r$个不同的素因子，根据莫比乌斯函数的定义有$\mu(d)=(-1)^r$。
$\sum\limits_{d|n} \mu(d)=1-\binom{k}{1}+\binom{k}{2} \cdots +(-1)^k \binom{k}{k}=(1-1)^k=0$
证毕。

设$\mu(n)$的前缀和为$M(n)=\sum\limits_{i \leq n} \mu(i)$。

那么有等式：

$\sum\limits_{1 \leq k \leq n} M(\left \lfloor \frac{n}{k} \right \rfloor) = 1$

成立。

证明：

$\sum\limits_{1 \leq k \leq n} M(\left \lfloor \frac{n}{k} \right \rfloor) = \sum\limits_{1 \leq k \leq n} \sum\limits_{1 \leq ik \leq n} \mu(i)=\sum\limits_{1 \leq j \leq n}\sum\limits_{i|j}\mu(\frac{j}{i})$

当$i$取遍$j$的所有约数的时候，$\frac{j}{i}$同样取遍$j$的所有约数。

所以$\sum\limits_{1 \leq j \leq n}\sum\limits_{i|j}\mu(\frac{j}{i})=\sum\limits_{1 \leq j \leq n}\sum\limits_{i|j}\mu(i)$

根据上面的引理，对于$2 \leq j \leq n$，$\sum\limits_{i|j}\mu(i)=0$。

所以$\sum\limits_{1 \leq j \leq n}\sum\limits_{i|j}\mu(i)=\mu(1)=1$

我们可以根据这个式子递归计算$M(n)$了。

具体代码实现的时候还有两点优化的地方：

$M(\left \lfloor \frac{n}{k} \right \rfloor)$值相同的$k$有多个，可以用区间分块加速。

为了避免重复计算，可以用哈希来实现记忆化递归。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        using namespace std;typedef long long LL;const int maxn = 20000000;const int MOD = 2333333;const int maxp = 1300000;int pcnt, prime[maxp];short mu[maxn];bool vis[maxn];struct Hash{    long long key;    int val, nxt;};Hash slot[MOD];int cnt, head[MOD];void preprocess() {    mu[1] = 1;    for(int i = 2; i < maxn; i++) {        if(!vis[i]) {            mu[i] = -1;            prime[pcnt++] = i;        }        for(int j = 0; j < pcnt && i * prime[j] < maxn; j++) {            vis[i * prime[j]] = true;            if(i % prime[j] != 0) mu[i * prime[j]] = -mu[i];            else {                mu[i * prime[j]] = 0;                break;            }        }    }    for(int i = 2; i < maxn; i++) mu[i] += mu[i-1];}void insert(long long key, int val) {    int ha = key % MOD;    slot[++cnt].key = key;    slot[cnt].val = val;    slot[cnt].nxt = head[ha];    head[ha] = cnt;}int M(long long n) {    if(n < maxn) return mu[n];    int ha = n % MOD;    for(int i = head[ha]; i; i = slot[i].nxt) {        if(slot[i].key == n) return slot[i].val;    }    int ans = 0;    for(LL i = 2, j; i <= n; i = j + 1) {        j = n / (n / i);        ans += (j - i + 1) * M(n / i);    }    ans = 1 - ans;    insert(n, ans);    return ans;}int main(){    preprocess();    long long a, b;    while(cin >> a >> b) {        printf("%d\n", M(b) - M(a-1));    }    return 0;}