【算法讲9：莫比乌斯函数及其反演（实践部分：详细入门）】

【算法讲9：莫比乌斯函数及其反演（实践部分）】

• 前置
• 补充
• 例题一：[HAOI2011]Problem b | 洛谷 P2522
• • 做法一：莫比乌斯反演
  • 做法二：套路做法
  • 核心代码
• 例题二：YY的GCD | 洛谷 P2257
• • 核心代码
  • 优化
  • • 优化修改处代码

好家伙，好多期的理论，终于可以实战一些题目了！

前置

• 【算法讲8：莫比乌斯函数及其反演（理论部分） | 欧拉筛】

补充

• 莫比乌斯反演，就是有算数函数 f ( n ) f(n) f(n) 和 F ( n ) F(n) F(n)，满足 F ( n ) = ∑ d ∣ n f ( d ) F(n)=\underset{d|n}{\sum}f(d) F(n)=d∣n∑​f(d) 或者 F ( n ) = ∑ n ∣ d f ( d ) F(n)=\underset{n|d}{\sum}f(d) F(n)=n∣d∑​f(d)

  然后，我们容易得到 F ( n ) F(n) F(n)，却不容易得到 f ( n ) f(n) f(n)，我们就可以用莫比乌斯反演得出 f ( n ) f(n) f(n)

• 当然，相同的题目做多了总有固定的套路，一道题目也有多种解法。

例题一：[HAOI2011]Problem b | 洛谷 P2522

• 【题目描述】洛谷 P2522

  给定正整数 a 、 b 、 c 、 d 、 k a、b、c、d、k a、b、c、d、k

  求 ： ∑ b i = a ∑ d j = c [ gcd ⁡ ( i , j ) = k ] \underset{i=a}{\overset{b}{\sum}}\underset{j=c}{\overset{d}{\sum}}[\gcd(i,j)=k] i=a∑b​​j=c∑d​​[gcd(i,j)=k]

• 【数据范围】

  样例组数 T ≤ 5 × 1 0 4 T\le 5\times 10^4 T≤5×104

  1 ≤ a ≤ b ≤ 5 × 1 0 4 1\le a\le b\le 5\times10^4 1≤a≤b≤5×104

  1 ≤ c ≤ d ≤ 5 × 1 0 4 1\le c\le d\le 5\times10^4 1≤c≤d≤5×104

• 【思路】第一题会讲的细一点

  暴力做的话时间复杂度 O ( T × b × d × log ⁡ ) O(T\times b\times d\times\log) O(T×b×d×log)，我们需要数论化简。

  考虑到原式求和上下标较复杂，我们考虑化简：

  （1） ∑ b i = a ∑ d j = c [ gcd ⁡ ( i , j ) = k ] \underset{i=a}{\overset{b}{\sum}}\underset{j=c}{\overset{d}{\sum}}[\gcd(i,j)=k] i=a∑b​​j=c∑d​​[gcd(i,j)=k] 简记为 A n s ( a , b , c , d ) Ans(a,b,c,d) Ans(a,b,c,d)，由容斥定理得到：

  A n s ( a , b , c , d ) = A n s ( 1 , b , 1 , d ) − A n s ( 1 , b , 1 , c − 1 ) − A n s ( 1 , a − 1 , 1 , d ) + A n s ( 1 , a − 1 , 1 , c − 1 ) Ans(a,b,c,d)=Ans(1,b,1,d)-Ans(1,b,1,c-1)-Ans(1,a-1,1,d)+Ans(1,a-1,1,c-1) Ans(a,b,c,d)=Ans(1,b,1,d)−Ans(1,b,1,c−1)−Ans(1,a−1,1,d)+Ans(1,a−1,1,c−1)

  （2）我们专注于化简 A n s ( 1 , m , 1 , n ) ： Ans(1,m,1,n)： Ans(1,m,1,n)：

做法一：莫比乌斯反演

• 我们设 f ( x ) = ∑ m i = 1 ∑ n j = 1 [ gcd ⁡ ( i , j ) = x ] f(x)=\underset{i=1}{\overset{m}{\sum}}\underset{j=1}{\overset{n}{\sum}}[\gcd(i,j)=x] f(x)=i=1∑m​​j=1∑n​​[gcd(i,j)=x]，即所有对中， gcd ⁡ ( i , j ) = x \gcd(i,j)=x gcd(i,j)=x 的数量。

• 我们设 F ( x ) = ∑ x ∣ d f ( d ) F(x)=\underset{x|d}{\sum}f(d) F(x)=x∣d∑​f(d)，即所有对中， gcd ⁡ ( i , j ) \gcd(i,j) gcd(i,j) 为 x x x 及其倍数的数量。

  容易想到， F ( x ) F(x) F(x) 我们非常容易算出来。

  为什么呢？因为只要求出 i ∈ [ 1 , m ] i\in[1,m] i∈[1,m]，有多少数字有因数 x x x ， j ∈ [ 1 , n ] j\in[1,n] j∈[1,n]，有多少数字有因数 x x x

  易得 F ( x ) = ⌊ m x ⌋ ⌊ n x ⌋ F(x)=\lfloor\frac{m}{x}\rfloor\lfloor\frac{n}{x}\rfloor F(x)=⌊xm​⌋⌊xn​⌋

  我们答案是什么？就是 f ( k ) f(k) f(k)。

• 接下来，根据莫比乌斯反演的第二种方法(见前置连接)，已知 F ( x ) F(x) F(x) 去求 f ( k ) f(k) f(k)：

  f ( k ) = ∑ k ∣ d μ ( d k ) F ( d ) = ∑ k ∣ d μ ( d k ) ⌊ m d ⌋ ⌊ n d ⌋ = ∑ min ⁡ ( m , n ) t = 1 μ ( t ) ⌊ m t k ⌋ ⌊ n t k ⌋ = ∑ min ⁡ ( ⌊ m k ⌋ , ⌊ n k ⌋ ) t = 1 μ ( t ) ⌊ m t k ⌋ ⌊ n t k ⌋ □ \begin{aligned} f(k)&=\underset{k|d}{\sum}\mu(\frac{d}{k})F(d)\\ &=\underset{k|d}{\sum}\mu(\frac{d}{k})\lfloor\frac{m}{d}\rfloor\lfloor\frac{n}{d}\rfloor\\ &=\underset{t=1}{\overset{\min(m,n)}{\sum}}\mu(t)\lfloor\frac{m}{tk}\rfloor\lfloor\frac{n}{tk}\rfloor\\ &=\underset{t=1}{\overset{\min(\lfloor\frac{m}{k}\rfloor,\lfloor\frac{n}{k}\rfloor)}{\sum}}\mu(t)\lfloor\frac{m}{tk}\rfloor\lfloor\frac{n}{tk}\rfloor\qquad \Box \end{aligned} f(k)​=k∣d∑​μ(kd​)F(d)=k∣d∑​μ(kd​)⌊dm​⌋⌊dn​⌋=t=1∑min(m,n)​​μ(t)⌊tkm​⌋⌊tkn​⌋=t=1∑min(⌊km​⌋,⌊kn​⌋)​​μ(t)⌊tkm​⌋⌊tkn​⌋□​

  第一行： 莫比乌斯反演第二个公式。

  第二行： 带入 F ( d ) F(d) F(d)

  第三行： 我们枚举 t = d k t=\frac{d}{k} t=kd​，得到 d = t k d=tk d=tk，带入即可。

  第四行： 上标等值变换。

  最后，整除分块即可。我们需要用到 莫比乌斯前缀和 ，数据范围较小，用欧拉筛筛一遍即可。

做法二：套路做法

• 根据一些套路，我们有这样的做法：

  ∑ m i = 1 ∑ n j = 1 [ gcd ⁡ ( i , j ) = k ] = ∑ ⌊ m k ⌋ i = 1 ∑ ⌊ n k ⌋ j = 1 [ gcd ⁡ ( i , j ) = 1 ] = ∑ ⌊ m k ⌋ i = 1 ∑ ⌊ n k ⌋ j = 1 ∑ d ∣ gcd ⁡ ( i , j ) μ ( d ) = ∑ min ⁡ ( ⌊ m k ⌋ , ⌊ n k ⌋ ) d = 1 μ ( d ) ∑ ⌊ m k ⌋ i = 1 [ d   ∣   i ] ∑ ⌊ n k ⌋ j = 1 [ d   ∣   j ] = ∑ min ⁡ ( ⌊ m k ⌋ , ⌊ n k ⌋ ) d = 1 μ ( d ) ⌊ m k d ⌋ ⌊ n k d ⌋ □ \begin{aligned} \underset{i=1}{\overset{m}{\sum}}\underset{j=1}{\overset{n}{\sum}}[\gcd(i,j)=k]&= \underset{i=1}{\overset{\lfloor\frac{m}{k}\rfloor}{\sum}}\underset{j=1}{\overset{\lfloor\frac{n}{k}\rfloor}{\sum}}[\gcd(i,j)=1]\\ &=\underset{i=1}{\overset{\lfloor\frac{m}{k}\rfloor}{\sum}}\underset{j=1}{\overset{\lfloor\frac{n}{k}\rfloor}{\sum}}\underset{d|\gcd(i,j)}{\sum}\mu(d)\\ &=\underset{d=1}{\overset{\min(\lfloor\frac{m}{k}\rfloor,\lfloor\frac{n}{k}\rfloor)}{\sum}}\mu(d)\underset{i=1}{\overset{\lfloor\frac{m}{k}\rfloor}{\sum}}[d\ |\ i]\underset{j=1}{\overset{\lfloor\frac{n}{k}\rfloor}{\sum}}[d\ |\ j]\\ &=\underset{d=1}{\overset{\min(\lfloor\frac{m}{k}\rfloor,\lfloor\frac{n}{k}\rfloor)}{\sum}}\mu(d)\lfloor\frac{m}{kd}\rfloor\lfloor\frac{n}{kd}\rfloor\qquad \Box \end{aligned} i=1∑m​​j=1∑n​​[gcd(i,j)=k]​=i=1∑⌊km​⌋​​j=1∑⌊kn​⌋​​[gcd(i,j)=1]=i=1∑⌊km​⌋​​j=1∑⌊kn​⌋​​d∣gcd(i,j)∑​μ(d)=d=1∑min(⌊km​⌋,⌊kn​⌋)​​μ(d)i=1∑⌊km​⌋​​[d ∣ i]j=1∑⌊kn​⌋​​[d ∣ j]=d=1∑min(⌊km​⌋,⌊kn​⌋)​​μ(d)⌊kdm​⌋⌊kdn​⌋□​

  等等…怎么就证出来了？我们细看每一行式子的推导过程。

  第一行： 这是一个等值变换，相当于问：原来 i = [ 1 , m ] i=[1,m] i=[1,m]，我们把所有有 k k k 这个因子的数字拿出来，然后除以 k k k ，相当于：若 k   ∣   i k\ |\ i k ∣ i，那么 i → 变 为 i k i\overset{变为}{\rightarrow} \frac{i}{k} i→变为ki​；对于 j j j 也是同理。然后，原来 gcd ⁡ ( i , j ) = k \gcd(i,j)=k gcd(i,j)=k 的数字都会变成 gcd ⁡ ( i k , j k ) = gcd ⁡ ( i , j ) k = 1 \gcd(\frac{i}{k},\frac{j}{k})=\cfrac{\gcd(i,j)}{k}=1 gcd(ki​,kj​)=kgcd(i,j)​=1

  第二行： 根据上一节的套路，我们已知了 [ gcd ⁡ ( i , j ) = 1 ] = ε ( gcd ⁡ ( i , j ) ) = ∑ d ∣ gcd ⁡ ( i , j ) μ ( d ) [\gcd(i,j)=1]=\varepsilon(\gcd(i,j))=\underset{d|\gcd(i,j)}{\sum}\mu(d) [gcd(i,j)=1]=ε(gcd(i,j))=d∣gcd(i,j)∑​μ(d)

  第三行： 更改求和顺序，枚举每一对 gcd ⁡ ( i , j ) \gcd(i,j) gcd(i,j) 的因子，相当于枚举每个因子，然后枚举每一对都是因子的倍数的 ( i , j ) (i,j) (i,j) 对。

  第四行： 1 ∼ ⌊ m k ⌋ 1\sim \lfloor\frac{m}{k}\rfloor 1∼⌊km​⌋有多少个数字满足有某个因子 d d d ？很简单，数字个数除以 d d d 然后向下取整即可。

  然后根据该式子： ⌊ ⌊ m k ⌋ d ⌋ = ⌊ m k d ⌋ \lfloor\frac{\lfloor\frac{m}{k}\rfloor}{d}\rfloor=\lfloor\frac{m}{kd}\rfloor ⌊d⌊km​⌋​⌋=⌊kdm​⌋

核心代码

• 时间复杂度 O ( n + T n ) O(n+T\sqrt n) O(n+Tn

  ​)

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 5e4+50;

bool vis[MAX];
ll prime[MAX];
ll mu[MAX];
ll premu[MAX];
int cnt;
void shai(int n){					/// 筛莫比乌斯函数
    mu[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
            vis[i*prime[j]] = 1;
            if(i % prime[j]){
                mu[i * prime[j]] = -mu[i];
            }else {
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
    for(int i = 1;i <= n;++i){		/// 求出莫比乌斯前缀和
        premu[i] = premu[i-1] + mu[i];
    }
}
ll solve(ll m,ll n,ll k){			/// 等价于前文 Ans(1,m,1,n)
    m = m / k;
    n = n / k;
    ll res = 0;
    ll L = 1;
    ll R = 0;
    while(L <= min(n,m)){
        R = min(n/(n/L),m/(m/L));
        res += (premu[R] - premu[L-1]) * (m / L) * (n / L);
        L = R + 1;
    }
    return res;
}
int main()
{
    shai(50000);
    int T;scanf("%d",&T);
    while(T--){
        ll a,b,c,d,k;
        scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
        ll res = 0;					/// 容斥
        res += solve(b,d,k);
        res -= solve(a-1,d,k);
        res -= solve(b,c-1,k);
        res += solve(a-1,c-1,k);
        printf("%lld\n",res);
    }
    return 0;
}
           

例题二：YY的GCD | 洛谷 P2257

• 【题目描述】洛谷 P2257

  求 ∑ n i = 1 ∑ m j = 1 [ gcd ⁡ ( i , j ) = P r i m e ] \underset{i=1}{\overset{n}{\sum}}\underset{j=1}{\overset{m}{\sum}}[\gcd(i,j)=Prime] i=1∑n​​j=1∑m​​[gcd(i,j)=Prime]

• 【数据范围】

  样例组数 T ≤ 1 0 4 T\le 10^4 T≤104

  1 ≤ n , m ≤ 1 0 7 1\le n,m\le 10^7 1≤n,m≤107

• 【思路】

  我们使用套路求法，做题可能会更快

  ∑ p ∈ P r i m e ∑ n i = 1 ∑ m j = 1 [ gcd ⁡ ( i , j ) = p ] = ∑ p ∈ P r i m e ∑ ⌊ n p ⌋ i = 1 ∑ ⌊ m p ⌋ j = 1 [ gcd ⁡ ( i , j ) = 1 ] = ∑ p ∈ P r i m e ∑ ⌊ n p ⌋ i = 1 ∑ ⌊ m p ⌋ j = 1 ∑ d ∣ gcd ⁡ ( i , j ) μ ( d ) = ∑ p ∈ P r i m e ∑ min ⁡ ( ⌊ n p ⌋ , ⌊ m p ⌋ ) d = 1 μ ( d ) ⌊ n p d ⌋ ⌊ m p d ⌋ = ∑ min ⁡ ( n , m ) T = 1 ∑ p ∣ T , p ∈ P r i m e μ ( T p ) ⌊ n T ⌋ ⌊ m T ⌋ = ∑ min ⁡ ( n , m ) T = 1 ⌊ n T ⌋ ⌊ m T ⌋ ∑ p ∣ T , p ∈ P r i m e μ ( T p ) □ \begin{aligned} \underset{p\in Prime}{\sum}\underset{i=1}{\overset{n}{\sum}}\underset{j=1}{\overset{m}{\sum}}[\gcd(i,j)=p] &= \underset{p\in Prime}{\sum} \underset{i=1}{\overset{\lfloor\frac{n}{p}\rfloor}{\sum}} \underset{j=1}{\overset{\lfloor\frac{m}{p}\rfloor}{\sum}} [\gcd(i,j)=1]\\ &= \underset{p\in Prime}{\sum} \underset{i=1}{\overset{\lfloor\frac{n}{p}\rfloor}{\sum}} \underset{j=1}{\overset{\lfloor\frac{m}{p}\rfloor}{\sum}} \underset{d|\gcd(i,j)}{\sum}\mu(d)\\ &= \underset{p\in Prime}{\sum} \underset{d=1}{\overset{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}{\sum}} \mu(d) \lfloor\frac{n}{pd}\rfloor \lfloor\frac{m}{pd}\rfloor\\ &= \underset{T=1}{\overset{\min(n,m)}{\sum}} \underset{p|T,p\in Prime}{\sum} \mu(\frac{T}{p}) \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor\\ &= \underset{T=1}{\overset{\min(n,m)}{\sum}} \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \underset{p|T,p\in Prime}{\sum} \mu(\frac{T}{p})\qquad \Box \end{aligned} p∈Prime∑​i=1∑n​​j=1∑m​​[gcd(i,j)=p]​=p∈Prime∑​i=1∑⌊pn​⌋​​j=1∑⌊pm​⌋​​[gcd(i,j)=1]=p∈Prime∑​i=1∑⌊pn​⌋​​j=1∑⌊pm​⌋​​d∣gcd(i,j)∑​μ(d)=p∈Prime∑​d=1∑min(⌊pn​⌋,⌊pm​⌋)​​μ(d)⌊pdn​⌋⌊pdm​⌋=T=1∑min(n,m)​​p∣T,p∈Prime∑​μ(pT​)⌊Tn​⌋⌊Tm​⌋=T=1∑min(n,m)​​⌊Tn​⌋⌊Tm​⌋p∣T,p∈Prime∑​μ(pT​)□​

  第一行： 我们依次枚举每一个质数 p p p

  第二行到第三行与前面套路相同。

  第四行： 考虑到我们枚举 p p p 又枚举 p p p 的所有倍数 p d pd pd，我们干脆直接设 T = p d T=pd T=pd，然后去枚举每一个 T T T。当然其中要求要有一个质因子 p p p ，此时 d = T p d=\frac{T}{p} d=pT​，把所有字母替换。

  第五行： 由于分块部分 ⌊ n T ⌋ ⌊ m T ⌋ \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor ⌊Tn​⌋⌊Tm​⌋ 与 p p p 无关了，我们把该项提到最前面。

  注意到最后一个部分 ∑ p ∣ T , p ∈ P r i m e μ ( T p ) \underset{p|T,p\in Prime}{\sum} \mu(\frac{T}{p}) p∣T,p∈Prime∑​μ(pT​) ，我们可以暴力枚举每一个 p p p，然后对于所有 p p p 的倍数 p k pk pk，我们都加上一个 μ ( p k p ) \mu(\frac{pk}{p}) μ(ppk​)，然后求一个前缀和即可参与分块运算。

  还有一点，这题大部分变量建议开 i n t int int ，前缀和比较大应该开 l l ll ll，否则会 T L E TLE TLE

核心代码

• 时间复杂度： O ( n log ⁡ n + T n ) O(n\log n+T\sqrt n) O(nlogn+Tn

  ​)

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e7+50;

bool vis[MAX];
int prime[MAX];
int mu[MAX];
int ff[MAX];
ll pre[MAX];
int cnt;
void shai(int n){
    mu[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
            vis[i*prime[j]] = 1;
            if(i % prime[j]){
                mu[i * prime[j]] = -mu[i];
            }else {
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
    for(int i = 1;i <= cnt;++i){
        int t = prime[i];
        while(t <= n){
            ff[t] += mu[t/prime[i]];
            t += prime[i];
        }
    }
    for(int i = 1;i <= n;++i)
        pre[i] = pre[i-1] + (ll)ff[i];
}
ll solve(int m,int n){
    ll res = 0;
    int L = 1;
    int R = 0;
    while(L <= min(n,m)){
        R = min(n/(n/L),m/(m/L));
        res += (pre[R] - pre[L-1]) * (m / L) * (n / L);
        L = R + 1;
    }
    return res;
}
int main()
{
    shai(10000000);
    int T;scanf("%d",&T);
    while(T--){
        int n,m;scanf("%d%d",&n,&m);
        printf("%lld\n",solve(n,m));
    }
    return 0;
}
           

• 用时：11.76s

  

优化

• 难道 ∑ p ∣ T , p ∈ P r i m e μ ( T p ) \underset{p|T,p\in Prime}{\sum} \mu(\frac{T}{p})\qquad p∣T,p∈Prime∑​μ(pT​) 只能 O ( n log ⁡ n ) O(n\log n) O(nlogn) 暴力算吗！事实表明不是这样。

  设 f ( i ) = ∑ p ∣ i , p ∈ P r i m e μ ( i p ) f(i)=\underset{p|i,p\in Prime}{\sum} \mu(\frac{i}{p})\qquad f(i)=p∣i,p∈Prime∑​μ(pi​)

  我们看看能否欧拉筛它！

• 假设 p p p 是 n n n 的最小质因数，假设 k k k 是质数。

  （1） f ( p ) = μ ( 1 ) = 1 f(p)=\mu(1)=1 f(p)=μ(1)=1

  （2） n = p × i n=p\times i n=p×i，当 p ⊥ i p\perp i p⊥i时 f ( i ) = ∑ k ∣ i μ ( i k ) f(i)=\underset{k|i}{\sum}\mu(\frac{i}{k}) f(i)=k∣i∑​μ(ki​)

  考虑到 f ( p × i ) = ∑ k ∣ p × i μ ( p × i k ) = ∑ k ∣ i μ ( i × p k ) + μ ( i × p p ) = − f ( i ) + μ ( i ) f(p\times i)=\underset{k|p\times i}{\sum}\mu(\frac{p\times i}{k})=\underset{k|i}{\sum}\mu(\frac{i\times p}{k})+\mu(\frac{i\times p}{p})=-f(i)+\mu(i) f(p×i)=k∣p×i∑​μ(kp×i​)=k∣i∑​μ(ki×p​)+μ(pi×p​)=−f(i)+μ(i)

  （3） n = p × i n=p\times i n=p×i，当 p ⊥̸ i p\not\perp i p​⊥i时

  考虑到当 k ≥ 2 k\ge2 k≥2 时 μ ( p k ) = 0 \mu(p^k)=0 μ(pk)=0

  当 i i i 的最小质因子 p p p 只有一个时，只有 μ ( p × i p ) = μ ( i ) \mu(\frac{p\times i}{p})=\mu(i) μ(pp×i​)=μ(i) ，其他 μ ( p × i k ) = 0 \mu(\frac{p\times i}{k})=0 μ(kp×i​)=0，故此时 f ( n ) = μ ( i ) f(n)=\mu(i) f(n)=μ(i)

  当 i i i 的最小质因子 p p p 不止一个时，所有 μ ( p × i k ) = 0 \mu(\frac{p\times i}{k})=0 μ(kp×i​)=0，不过此时 μ ( i ) = 0 \mu(i)=0 μ(i)=0，也满足 f ( n ) = 0 = μ ( i ) f(n)=0=\mu(i) f(n)=0=μ(i)

优化修改处代码

时间复杂度： O ( n + T n ) O(n+T\sqrt n) O(n+Tn

​)

const int MAX = 1e7+50;

bool vis[MAX];
int prime[MAX];
int mu[MAX];
int ff[MAX];
ll pre[MAX];
int cnt;
void shai(int n){
    mu[1] = 1;
    ff[1] = 0;
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            prime[++cnt] = i;
            mu[i] = -1;
            ff[i] = 1;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
            vis[i*prime[j]] = 1;
            if(i % prime[j]){
                mu[i * prime[j]] = -mu[i];
                ff[i * prime[j]] = -ff[i] + mu[i];
            }else {
                mu[i * prime[j]] = 0;
                ff[i * prime[j]] = mu[i];
                break;
            }
        }
    }
    for(int i = 1;i <= n;++i)
        pre[i] = pre[i-1] + (ll)ff[i];
}
           

• 用时：8.47s