本文主要介绍简单的积性函数入门，所作证明可能不够严谨，但足够通俗具体。希望能为同学们提供一点帮助。

不重要的碎碎念：
本次写下这篇文章的主要是因为在结训赛中遇到了一道题目却没有做出来，想来从一开始学习欧拉筛就没有好好听，所以干脆趁着这几天抽出时间从最基础的部分开始学习。

题目链接：
E - 简单的求最大公约数(hard)

什么是积性函数

在数论中，积性函数是指一个定义域为正整数n的算术函数f(n)，有如下性质：f(1) = 1，且当a 和b 互质时，f(ab) = f(a) f(b)。

若一个函数f(n) 有如下性质：f(1) = 1，且对两个随意正整数a ,b 而言，不只限这两数互质时，f(ab) = f(a)f(b) 都成立，则称此函数为完全积性函数。

而积性函数f(ab) = f(a)f(b)的性质为我们由小数据推出大数据的实现创造了可能，因此我们可以用f(3)f(5)推出f(15)的值。

但是对于每一种积性关系，他们的具体关系实际上是不同的，因此我们需要单独来看每一种关系。

从埃筛说起

vector<bool> isp(N,true);
vector<int> primes;
void eratosthenes(int n){
    isp[0] = isp[1] = false;
    for(int i=2;i<=n;i++){
        if(isp[i]){
            primes.push_back(i);
            for(int j=2*i;i<n;j+=i){
                isp[j]=false;
            }           
        }
    }
}

埃筛对于每个数都进行遍历，将质数的倍数进行标记，这样此次i更新到isp[i]为true时说明这个数前面没有她的因子，遂这个数一定是素数。

埃筛有个重要的思想就是用前面的标记后面的数据。

理解欧拉筛

vector<bool> isp(N,true);
vector<int> primes;
void get_prime(int n){
    isp[0] = isp[1] = false;
    for(int i=2;i<=n;i++){
        if(isp[i])primes.push_back(i);
        for(auto p:primes){
            if(p*i>n)break;
            isp[p*i]=false;
            if(i%p==0){
                break;
            }
        }
    }
}

欧拉筛是枚举每一位 i 如果没有被标记，他就是一个质数，然后放到 primes 里面。

然后枚举 i 的质数倍将其全部标记为false。

首先我们不理会 if(i%j==0) 这一行。例如当i枚举到5时，我们会标记2*5，3*5，也就是10，15。当我们枚举i到4时，我们会标记2*4，3*4，也就是8，12。

但是这时候我们会发现2*4的最小质因数时2，接下来3*4，4*4，5*4，6*4……的最小质因数都是2，这是为什么呢？因为4的最小质因数就是2！这里就是关键部分了，当我们枚举到i的最小质因数时（也就是所谓的 if(i%j==0) ），我们就可以退出标记了，而每个合数肯定能变成最小质因数*某个数的形式，所以合数会被标记上。

那这时候可能有同学会问：那提前退出不会漏掉标记吗，12会不会不被标记上呢？答案是会被标记上的，任何一个数都能分解成质数乘另一个数，即n=p*i（p表示最小质因子，i表示正在枚举的i，从1枚举到当前的i）的形式，而这个i一定是在n之前被枚举过的，所以如果n是合数就一定会被标记。例如12=2*6,12会在i枚举到6的时候被标记

欧拉筛给我们的启示就是如何让每个数只被最小的质因子筛掉。

四大积性函数

欧拉函数，莫比乌斯函数，约数个数函数，约数合数函数均为积性函数，也就是满足f(ab) = f(a) f(b)，此处略去证明等之后再来填坑（请注意公式只有在ab互质时成立，与完全积性函数进行区分）。

模板：

#include<cstdio>
using namespace std;
#define IL inline 
typedef long long LL;
const int N = 1e6 + 3;
bool np[N];
int pri[N],phi[N],mu[N],di[N],si[N];
IL int Euler_sieve(int n) {
    int tot = 0;
    phi[0] = mu[0] = di[0] = si[0] = 0;
    np[1] = phi[1] = mu[1] = di[1] = si[1] = 1;
    for(int i=2;i<=n;i++) {
        if(!np[i]) {
            pri[++tot] = i;
            phi[i] = i-1;
            mu[i] = -1;
            di[i] = 2;
            si[i] = i + 1;
        }
        for(int j=1;j<=tot&&i*pri[j]<=n;j++) {
            np[i*pri[j]] = true;
            if(i % pri[j] == 0) {
                phi[i*pri[j]] = pri[j] * phi[i];
                mu[i*pri[j]] = 0;
                di[i*pri[j]] = (di[i] << 1) - di[i/pri[j]];
                si[i*pri[j]] = si[i] + pri[j] * (si[i]-si[i/pri[j]]);
                break;
            }
            phi[i*pri[j]] = phi[i] * (pri[j]-1);
            mu[i*pri[j]] = -mu[i];
            di[i*pri[j]] = di[i] << 1;
            si[i*pri[j]] = si[i] * (1+pri[j]);
        }
    }
    return tot;
}

前置定理

算数基本定理（其中p均为质数）

$$ N=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\ldots \ldots p_{n}^{k_{n}} $$

欧拉函数

维基百科定义

欧拉函数（Euler's Totient Function），也称为φ函数或欧拉φ函数，记作 $\varphi(n)$，用于表示小于或等于 ( n ) 的正整数中，与 ( n ) 互质的数的个数。一个数 ( a ) 与 ( n ) 互质的定义是 $ \gcd(a, n) = 1 $，其中 gcd 表示最大公约数。

1.一个质数p的欧拉函数一定是p-1。

2.接下来我们研究一类特殊的数$ p^k $，其中p是质数，则其满足

$$ \varphi \left( p^{k}\right) =p^{k}-p^{k-1}=(p-1)/p*p^k $$

因为$p^k$仅有质因数k，所以与其不互质的仅有p的倍数，而在$1-p^k$这个区间内共有$p^k/p=p^{k-1}$个p的倍数。相减直接得到与$p^k$互质的数字个数。

3.再根据积性函数性质，对于每个数，我们都可以通过算数基本定理将其进行分解 并提取出来$p^k$

$$ \varphi \left( N\right) =\varphi \left( p_{1}^{k_{1}} \right) \varphi \left( p_{2}^{k_{2}} \right)\cdots\varphi\left(p_{n}^{k_{n}}\right)=N\prod _{ p| d}\left( \dfrac{p-1}{p}\right) $$

此公式中p均为质数

仿照欧拉筛的性质，有如下情况

1.i为质数，将 phi[i] 标记

2.然后在素数表中对每个p筛选。

• 若i与p互质，则直接相乘可以得到 phi[i*p]=phi[i]*phi[p]
• 若 i%p==0 即i是p的倍数，这时积性函数的性质就不成立了，此时关系应该是phi[ip]=phi[i]p。

莫比乌斯函数

莫比乌斯函数的定义是

$$ \mu \left( n\right) =\begin{cases}1,\eta =1\\ 0,\exists d:d^{2}| n\\ \left( -1\right) ^{w\left( n\right) },otherwise\end{cases} $$

其中$w(n)$表示质因子的个数，例如30=2*3*5。则$\mu(30)=-1$。

同样，计算莫比乌斯函数也有三种情况：

1.i是质数，mu[i]是-1
2.在素数表中枚举p

• 若i与p互质，则直接相乘可以得到 mu[i*p]=mu[i]*mu[p]
• 若 i%p==0 即i是p的倍数，这时积性函数的性质就不成立了，根据定义必然有 mu[i*p]=0

约数个数函数

约数个数函数表示N的约数个数，根据算数基本定理，每个$k_i$的取法都确定了一个约数，所以我们可以通过计算

$$ \prod_{i=1}^{n} (k_i + 1)\\ = (k_1 + 1)(k_2 + 1) \cdots (k_n + 1) $$

得到约数个数。显然这也是一个积性函数。

对于约数个数我们也有三种情况：

1.i是质数，di[i]是2

2.在素数表中枚举p

• 若i与p互质，则直接相乘可以得到 di[i*p]=di[i]*di[p]
• 若 i%p==0 即i是p的倍数，这时积性函数的性质就不成立了。

$$d\left(i*p_i\right)=\left(k_1+2\right)\left(k_2+1\right)\left(k_3+1\right)\cdots\left(k_n+1\right)$$

$$=2\left(1+k_1\right)\left(1+k_2\right)\cdot\left(1+k_n\right)-k_1\left(1+k_2\right)\left(1+k_3\right)\cdots\left(1+k_n\right)$$

$$=2d\left(i\right)-d\left(\dfrac{i}{p}\right)$$

约数和函数

约数和公式是用于计算一个数的所有约数之和的公式。这个数 ( n ) 的所有约数之和的公式为：

$$ \sigma(n) = (1 + p_1 + p_1^2 + \cdots + p_1^{e_1})(1 + p_2 + p_2^2 + \cdots + p_2^{e_2}) \cdots (1 + p_k + p_k^2 + \cdots + p_k^{e_k}) $$

可表示为：

$$ \sigma(n) = \prod_{i=1}^{k} \left( \sum_{j=0}^{k_i} p_i^j \right) $$

例如，对于 ( n = 28 )，它的质因数分解是 $( 28 = 2^2 \times 7^1 )$，所以它的约数和为：

$$ \sigma(28) = (1 + 2 + 2^2)(1 + 7) = (1 + 2 + 4)(1 + 7) = 7 \times 8 = 56 $$

所以，28的所有约数之和为56。

1.i是质数，si[i]是-1
2.在素数表中枚举p

• 若i与p互质，则直接相乘可以得到 si[i*p]=si[i]*si[p]
• 若 i%p==0 即i是p的倍数，这时积性函数的性质就不成立了，有 si[i*p]=0。推导过程在这