莫比乌斯反演&杜教筛&Min_25筛

莫比乌斯反演

• 莫比乌斯函数

$$\mu(x)= \begin{cases} 1,(x=1)\\ (-1)^k,(x=p_1p_2…p_k)\\ 0,(\text{其他情况}) \end{cases}$$

其中 $p_1p_2…p_k$ 代表有 $k$ 个素数相乘，或者说可以分解成 $k$ 个素数。

性质：

$$\sum_{d|n}{\mu(d)}= \begin{cases} 1,n=1\\ 0,n\not=1 \end{cases} \Rightarrow \sum_{d|n}{\mu(d)}=[n=1]$$

• 积性函数

$f(1)=1,f(pq)=f(p)\times f(q)$（$p,q$ 互质）

$\phi(x)$ 欧拉函数。

$\mu(x)$ 莫比乌斯函数。

$\gcd(n,k)$，$k$ 一定的最大公因数。

• 完全积性函数

$f(1)=1,f(ab)=f(a)\times f(b)$（$a,b$ 任意）

$\epsilon(n)$ 单位函数也是 $[n=1]$（单位函数和某函数“卷”还是某函数）

（基本都是符合正常运算的函数，不是特殊方式搞出数值的函数。）

• 狄利克雷卷积

$$(f * g)(n)=\sum_{d|n}{f(d)g(\frac{n}{d})}$$

其中 $(n)$ 一般省略不写，狄利克雷卷积满足一些运算：

交换律：

$$f * g=g * f$$

结合律：

$$(f * g) * h=f * (g * h)$$

分配律：

$$f * (g+h)=f * g+f * h$$

明白它是一种运算，即常见运算律即可。

• 莫比乌斯反演两种形式

$$F(n)=\sum_{d|n}{f(d)}\Rightarrow f(n)=\sum_{d|n}{\mu(d)F(\frac{n}{d})}$$

另一种形式：

$$F(n)=\sum_{n|d}f(d)\Rightarrow f(n)=\sum_{n|d}{\mu( \frac{d}{n})F(d)}$$

讲道理，这玩意背过就好，要用的时候直接套就行。

• 莫比乌斯反演证明

$$\sum_{d|n}{\mu{(d)}=[n=1]}\Rightarrow \mu * 1=\epsilon$$ $$F(n)=\sum_{d|n}{f(d)}\Rightarrow F=f * 1$$ $$F * \mu=f * 1 * \mu=f * \epsilon=f$$ $$f=F * \mu$$ $$f(n)=\sum_{d|n}{\mu(d)F(\frac{n}{d})}$$

杜教筛

• 公式推导：

首先有一个积性函数 $f(x)$，然后我们要求它的前缀和。即：

$$S(n)=\sum_{i=1}^n{f(i)}$$

现在构造两个积性函数 $h,g$ 并且满足 $h= g * f$（注意整两个积性函数是我们现“捏”出来的）。

根据狄利克雷卷积：

$$h(i)=\sum_{d|n}{g(d)f(\frac{i}{d})}$$

现在我们要求 $h(i)$ 的前缀和，即：

$$\sum_{i=1}^n{h(i)}=\sum_{i=1}^n\sum_{d|i}^i{g(d)f(\frac{i}{d})}$$

为了方便理解，我们现在稍微变化一下：

$$=\sum_{i=1}^n(\sum_{d|i}^i{g(d)f(\frac{i}{d})})$$

假设，当前的 $i=k$ 有因数 $1,a,b,c,k$，其中 $ac=k,b^2=k$ 如果展开括号里的求和符号就是：

$$=\sum_{d|k}^k{g(d)f(\frac{k}{d})}$$ $$=g(1)f(k)+g(a)f(c)+g(b)f(b)+g(c)f(a)+g(k)f(1)$$

现在我们只展开了第一个求和符号的一个值 $i=k$ 是的情况。

那如果所有的值 $1\le i\le n$ 全部展开（有些抽象，想象一下），那么就会出现可以合并的项例如：

$$g(1)f(i_1)+g(1)f(i_2)=g(1)(f(i_1)+f(i_2))$$ $$g(a)f(c)+g(a)f(\frac{i_3}{a})=g(a)(f(c)+f(\frac{i_3}{a}))$$

其中 $a|i_3$。

所以可以得到：

$$\sum_{d=1}^n{g(d)\sum_{d|i}^n{f(\frac{i}{d})}}$$

此时的 $i$ 只有是 $d$ 的倍数（$i|d$）时才“有用”。

所以：

$$\sum_{i=1}^n\sum_{d|i}^i{g(d)f(\frac{i}{d})}=\sum_{d=1}^n{g(d)\sum_{d|i}^n{f(\frac{i}{d})}}$$

而这一步就是“杜教筛变换”。

我们知道了 $i$ 有用的“条件”，而且在 $n$ 以内，只有 $\lfloor\frac{n}{d}\rfloor$ 个数，$i$ 是有用的。那么我么直接将 $i$ 换种表示：

$$=\sum_{d=1}^n{g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{f(i)}}$$

在我们一开始，有：

$$S(n)=\sum_{i=1}^n{f(i)}$$

所以，又可以写为：

$$=\sum_{d=1}^n{g(d)S(\lfloor\frac{n}{d}\rfloor)}$$

得到：

$$\sum_{i=1}^n{h(i)}=\sum_{d=1}^n{g(d)S(\lfloor\frac{n}{d}\rfloor)}$$

现在我们将 $i=1$ 的情况提出来（现在要求递推式，方便编程实现。）：

$$g(1)S(n)=\sum_{i=1}^n{h(i)-\sum_{i=2}^n{g(i)S(\lfloor\frac{n}{i}\rfloor)}}$$

我们现在就可以递推求 $S(i)$ 了，其中 $h,g$ 是我们自己“捏”出来了。我们单独构造即可。

杜教筛复杂度：$O(n^{\frac{2}{3}})$（这里就不证明了。）

欧拉函数前缀和

首先要了解一个公式：

$$n=\sum_{d|n}{\phi(d)}$$

有没有感到很眼熟？狄利克雷卷积：

$$h=f * g=\sum_{d|n}{f(d)g(\frac{n}{d})}$$

此时我们将 $h(i)=n$ 代表第 $n$ 个数，$g(\frac{n}{d})=1$ 常函数。

那么：

$$n=\sum_{d|n}{\phi(d)}\Rightarrow h=\sum_{d|n}{\phi(d)}$$

求前缀和：

$$S(n)=\sum_{i=1}^n{h(i)}=\sum_{i=1}^n{\sum_{d|n}{\phi(d)}}$$

根据我们上面推过的杜教筛公式：

$$g(1)S(n)=\sum_{i=1}^n{h(i)-\sum_{i=2}^n{g(i)S(\lfloor\frac{n}{i}\rfloor)}}$$

带入：

$$S(n)=\sum_{i=1}^n{i}-\sum_{i=2}^n{S(\lfloor\frac{n}{i}\rfloor)}$$ $$=\frac{n(n+1)}{2}-\sum_{i=2}^n{S(\lfloor\frac{n}{i}\rfloor)}$$

莫比乌斯函数前缀和

莫比乌斯函数有类似性质：

$$\sum_{d|n}{\mu(d)}=[n=1]$$

所以：$h=\epsilon,g=1$（$\epsilon$ 元函数，见上文，除了 $\epsilon(1)=1$，其他情况为 $0$）

$$S(n)=\sum_{i=1}^n{\epsilon(i)}-\sum_{i=2}^n{S(\lfloor\frac{n}{i}\rfloor)}$$ $$=1-\sum_{i=2}^n{S(\lfloor\frac{n}{i}\rfloor)}$$

代码

• 欧拉函数处理已经出现的质数因子情况

$$\phi(x)=x\prod_{p|x}{(1-\frac{1}{p})}$$

而每种质因子只会作出一次影响。所以：

$$\phi(6)=6\times(1-\frac{1}{2})\times(1-\frac{1}{3})$$ $$\phi(12)=12\times (1-\frac{1}{2})\times (1-\frac{1}{3})=2\times \phi(6)$$

所以在统计 $\phi(12)$ 时，可直接在 $\phi(6)$ 上“搞事情”。因为 $2$ 已经做过“贡献”了。

本题略微卡常，记得开 long long。

P4213 【模板】杜教筛（Sum）

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
#include<bitset>
#include<map>
using namespace std;
int r_r(){//快读 
    int k=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*f;
}
const int o_o=5e6+10;//比 题目要求 n 的 2/3 大即可 
int z_z[o_o];//记录质数
bool b_b[o_o];
int m_u[o_o];//莫比乌斯函数值
map<long long,long long> s_m;//莫比乌斯函数前缀和
map<long long,long long> s_p;//欧拉函数前缀和
long long p_i[o_o];//欧拉函数值
void yv(){
    int x_p=0;
  b_b[0]=b_b[1]=1;
  m_u[1]=p_i[1]=1;//初始化 1 情况 
  for(int i=2;i<o_o;i++){
    if(!b_b[i]){
            z_z[x_p++]=i;//记录质数 
            m_u[i]=-1;//初始化莫比乌斯函数的质数值 
            p_i[i]=i-1;//初始化欧拉函数的质数值 
        }
    for(int j=0;j<x_p&&i*z_z[j]<o_o;j++){
      b_b[i*z_z[j]]=1;//标记合数 
      if(i%z_z[j]){
        m_u[i*z_z[j]]=-m_u[i];//处理莫比乌斯函数 
        p_i[i*z_z[j]]=p_i[i]*p_i[z_z[j]];//处理欧拉函数 
      }else{
        m_u[i*z_z[j]]=0;//莫比乌斯函数其他情况处理 
        p_i[i*z_z[j]]=p_i[i]*z_z[j];//欧拉函数处理已经出现的质数因子情况  
        break;
      }
    }
  }
  for(int i=1;i<o_o;i++){//前缀和
        m_u[i]+=m_u[i-1];
        p_i[i]+=p_i[i-1];
    }
}
int g_m(int x){
  if(x<o_o)return m_u[x];//直接返回预处理的值 
  if(s_m[x])return s_m[x];//读取记忆化
  int a_s=1;
  for(long long l=2,r;l<=x;l=r+1){
    r=x/(x/l);//分块 
    a_s-=(r-l+1)*g_m(x/l);//减去快内“贡献” 
  }
  return s_m[x]=a_s;//记忆化 
}
long long g_p(long long x){
  if(x<o_o) return p_i[x];//直接返回预处理的值 
  if(s_p[x]) return s_p[x];//读取记忆 
  long long a_s=1LL*x*(x+1)>>1;
  for(long long l=2,r;l<=x;l=r+1){
    r=x/(x/l);//分块 
    a_s-=(r-l+1)*g_p(x/l);//减去块内“贡献” 
  }
  return s_p[x]=a_s;//记忆化 
}
int main(){
  yv();
  int t=r_r();
  while(t--){
    int n=r_r();
    printf("%lld %d\n",g_p(n),g_m(n));//输出结果 
  }
  return 0;
}

Min_25 筛

主角来了！

时间复杂度 $O(\frac{n^{\frac{3}{4}}}{\log n})$

但是有适用要求：

$f(p)$ 是一个关于质数 $p$ 的且可以快速求。

$f(p^x)$ 可以快速求。

例如，这种题目：P5325 【模板】Min_25筛

假设

$$h=\sum_{i=1}^n{f(i)}$$

将 $h$ 分成两部分求：质数，合数。

$$g(n,j)=\sum_{i=1}^n{i\text{(是质数或最小质因子大于 $j$ 的合数)}}$$

大概介绍一下 $g(n,j)$（这个要是没看懂，后面没法学）：

原数：      2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
最小质因子: 2 3 2 5 2 7 2 3  2 11  2 13  2  3  2 17  2 19  2  3  2 23  2  5  2  3  2 29  2
g(30,1):    1 1 0 1 0 1 0 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  
g(30,2):    1 1 0 1 0 1 0 0  0  1  0  1  0  0  0  1  0  1  0  0  0  1  0  1  0  0  0  1  0
g(30,3):    1 1 0 1 0 1 0 0  0  1  0  1  0  0  0  1  0  1  0  0  0  1  0  0  0  0  0  1  0

（可能需要调整网页缩放看全表）

首先注意的是 $g(n,j)$ 中的 $j$ 代表的是第 $j$ 小的质数。统计的是质数或最小质因子 $> j$ 的数的个数。

不难发现 $j$ 越大， $g(n,j)$ 越小，那么如果我们就要找到 $g(n,j-1)$ 和 $g(n,j)$ 之间的关系。我们刚刚已经说明了 $g(n,j)$ 统计的是什么，所以将做小质因子是 $j$ 的数减去即可，但是保留质数，因为质数是全要的。

然后我们通过递推 $g(n,0)$ 到 $g(n,+\infty)$。

$$g(n,j)= \begin{cases} g(n,j-1),p_j^2>n\\\\ g(n,j-1)-F(p_j)\times (g(\lfloor\frac{n}{p_j}\rfloor,j-1)-\sum_{i=1}^{j-1}{F(p_j)}),p_j^2\le n \end{cases}$$

现在我们定义一个新函数：

$$S(n,j)=\sum_{i=1}^n{f(i)\text{（$i$ 的最小质因子大于第 $j$ 个素数）}}$$

题目要我们求得结果变为 $S(n,0)+f(1)$。

那么先看一下结果式：

$$S(n,j)=g(n,|P|)-\sum_{i=1}^{j}{f(p_i)}+\sum_{k=j+1}^{p_{k}^{2}\le n}{\sum_{e=1}^{p_k^e\le n}{f(p_k^e)(S(\lfloor\frac{n}{p_k^e}\rfloor,k)+[e > 1])}}$$

$g(n,|P|)$ 是 $n$ 以内的质数和（暂时可以当成上文说的 $g(n,+\infty)$）

考虑合数：

从 $j+1$ 个质数（$p_k$）开始枚举的一个合数的最小质因子。同时枚举它的幂（也算是一种分块吧，每块长 $p_k$）要注意 $e$ 的存在，因为 $e=1$ 时，是素数本身，所以是合数时才加上贡献。

$$\sum_{k=j+1}^{p_{k}^{2}\le n}{\sum_{e=1}^{p_k^e\le n}{f(p_k^e)(S(\lfloor\frac{n}{p_k^e}\rfloor,k)+[e > 1])}}$$

这一块就是在处理合数部分，前面在处理素数部分（这么一看是不是简单了不少。）

回归题目，题目让我们给的是：$f(p^k)=p^k(p^k-1)$

$$f(p^1)=p^1(p^1-1)$$

那我们要预处理一下质数 $1,2$ 次的前缀和（$\sqrt{n}$ 的线性筛范围即可）。

在整数分块时，童谣需要统计前缀和，不过直接公式即可：

$1$ 次幂：

$$\frac{n(n+1)}{2}$$

$2$ 次幂：

$$\frac{n(n+1)(2n+1)}{6}$$

注意减去指质数本身的贡献，剩下的套公式处理即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
#include<bitset>
using namespace std;
long long r_r(){//快读 
    long long k=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*f;
}
const long long m_d=1000000007;//模数 
long long k_m(long long a,long long b){//快速幂 
  long long r_s=1;
  while(b){
    if(b&1)r_s=(r_s*a)%m_d;
    a=(a*a)%m_d;
    b>>=1;
  }
  return r_s;
} 
long long v_2=k_m(2,m_d-2),v_6=k_m(6,m_d-2);//乘法逆元 
const int o_o=1e6+10;
long long z_z[o_o];//存储素数 
int x_z;//素数排名 
int s_1[o_o],s_2[o_o];//1,2 次的素数前缀和 
long long n;
long long s_q;//预估长度 
long long t_t;//存储块的数量 
long long g_1[o_o],g_2[o_o];//1,2 次整数分块的前缀和 
long long w[o_o];//块值 
long long i_1[o_o],i_2[o_o];//存块的下标，为了防止溢出，大于预估长度反过来存 
bool b_b[o_o];//素数筛判断 
void yv(int n){
    b_b[1]=1;
    for(int i=1;i<=n;i++){//线性筛 
        if(!b_b[i]){
            z_z[++x_z]=i;//记录质数 
            s_1[x_z]=(s_1[x_z-1]+i)%m_d;//质数前缀和 
            s_2[x_z]=(s_2[x_z-1]+1ll*i*i)%m_d;//质数平方前缀和 
        }
        for(int j=1;j<=x_z&&z_z[j]*i<=n;j++){
            b_b[i*z_z[j]]=1;
            if(i%z_z[j]==0)break;
        }
    }
}
long long g_a(long long x,int y){
    if(z_z[y]>=x)return 0;
    long long k=x<=s_q?i_1[x]:i_2[n/x];//处理下标 
    long long a_s=(g_2[k]-g_1[k]+m_d-(s_2[y]-s_1[y])+m_d)%m_d;//处理素数部分 
    for(int i=y+1;i<=x_z&&z_z[i]*z_z[i]<=x;i++){//处理合数部分 
        long long x_x=z_z[i];
        for(int j=1;x_x<=x;j++,x_x=x_x*z_z[i]){
            long long k_k=x_x%m_d;
            a_s=(a_s+k_k*(k_k-1)%m_d*(g_a(x/x_x,i)+(j>1)))%m_d;
        }
    }
    return a_s%m_d;
}
int main(){
  n=r_r();
    s_q=sqrt(n);//预估处理的数据范围 
    yv(s_q);//线性筛素数 
    for(long long i=1,j;i<=n;i=j+1){
        j=n/(n/i);//分块 
        w[++t_t]=n/i;//保存分块的值（处理的数的数量） 
        g_1[t_t]=w[t_t]%m_d;
        g_2[t_t]=g_1[t_t]*(g_1[t_t]+1)%m_d*v_6%m_d*(2*g_1[t_t]+1)%m_d-1;//2 次方整数分块前缀和 
        g_1[t_t]=g_1[t_t]*(g_1[t_t]+1)%m_d*v_2%m_d-1;//1 次方整数分块前缀和 
        if(n/i<=s_q)i_1[n/i]=t_t;//返回内下标 
        else i_2[n/(n/i)]=t_t;//值可能会过大，反过来存下标（保证空间复杂度） 
    }
    for(int i=1;i<=x_z;i++){//递推到“无穷” 
        for(int j=1;j<=t_t&&z_z[i]*z_z[i]<=w[j];j++){
            long long k=w[j]/z_z[i]<=s_q?i_1[w[j]/z_z[i]]:i_2[n/(w[j]/z_z[i])];//找回下标 
            g_1[j]=(g_1[j]+m_d-z_z[i]*(g_1[k]-s_1[i-1]+m_d)%m_d)%m_d;//递推 1 次项 
            g_2[j]=(g_2[j]+m_d-z_z[i]*z_z[i]%m_d*(g_2[k]-s_2[i-1]+m_d)%m_d)%m_d;//递推 2 次项 
        }
    }
    printf("%lld\n",(g_a(n,0)+1)%m_d);//结果加上 f(1) 输出即可 
    return 0;
}