素数

定义

请自行百度。。。

质数的判定

1. 试除法

若一个正整数$N$为合数，则存在一个能整除$N$的正整数$T$，其中$ 2≤T≤\sqrt{N} $

证明：略

简易代码：

bool prime_judge(int x)
{
    if(x<2) return false;
    for(int i=2;i*i<=x;++i)
        if(x%i==0) return false;
    return true;
}

复杂度：显而易见试除法的时间复杂度为 $O(\sqrt{N})$ .

至于 \(Miller-Robbin\)算法 ，戳这里。

质数筛法

即给定一个整数$N$，求出1~$N$之间所有质数

1. $Eratosthenes$筛法

算法思想：

任意整数$x$的倍数$2x$、$3x$ $\cdots$ 均不是质数

实现步骤：

从$2$开始，一直扫到$N$，把他们的倍数 $2x$、$3x$、 $\cdots$ 、$\left \lfloor \frac{N}{x} \right \rfloor * x$ 标记为不是质数。

若扫到某个数没有被标记，则该数是质数。

简易代码：

void make_prime_list(int n)
{
    memset(vis,false,sizeof vis);
    for(int i=2;i<=n;++i)
    {
        if(vis[i]) continue;
        printf("%d ",i);
        for(int j=i;i*j<=n;++j) vis[i*j]=1;
    }
}

复杂度：蓝书上写的是 \(O(\sum_{质数p≤N} \frac{N}{p}) = O(N\log \log N)\) （其实我也不太会证明）

2. 线性筛法（欧拉筛）

优化原理：

我们发现，上述筛法中不可避免的要对一个数重复标记。如：$12$ 既会被 $6*2$ 筛掉，也会被 $4*3$ 筛掉。如图：

那么有没有什么办法可以对每个数只筛一次呢？答案是肯定的。

我们可以只用每个数的最小质因子去筛它。

线性筛法实现步骤

• 首先从 \(2\)~\(N\) 循环一遍

• 若 \(i\) 没有被标记，则将它加入质数表中

• 扫描已有的小于 \(\left \lfloor \frac{N}{i} \right \rfloor\) 的质数 \(p_j\) ，标记 \(i*p_j\) ；当 \(p_j\) 可以整除 \(i\) 时，则说明此时 \(p_j\) 已不是 \(i*p_j\)的最小质因子，即跳出循环。

优化后的标记过程（如取 $N=20$）：

简易代码：

void make_prime_list(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!vis[i]) pri[++tot]=i;
        for(int j=1;j<=tot && pri[j]*i<=n;++j)
        {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}

时间复杂度：因为每个合数 $i*p_j$ 只会被它的最小质因子 $p_j$ 筛一次，所以时间复杂度为 $O(N)$ 。

算术基本定理

• 定义：算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法只有一种方式。

• 用数学语言表示，即为：\(\forall A\in\mathbb{N},\,A>1\ \exists \prod_{i=1}^n p_i^{a_i}=A\)。其中 \(p_1<p_2<p_3<\cdots<p_n\) 且 \(p_i\) 为一个质数，\(a_i\in\mathbb{Z}^+\)。

• 推论：见\(2.2\)。

质因数分解

1. 试除法

• 由算术基本定理可得，将\(\left[2,\sqrt{N}\right]\)的数扫一遍，其中必然可以将 \(N\) 的质因子从小到大地除去。

• 复杂度：显而易见的是 \(O(\sqrt{N})\) 。

• 简易代码：

const int N=100005;
int pri[N],count[N],n;
inline void prime_divide(int n)
{
    int cnt=0;
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            pri[++cnt]=i,count[cnt]=0;
            while(n%i==0) n/=i,++count[cnt];
        }
    }
    if(n>1) pri[++cnt]=n,count[cnt]=1;
    for(int i=1;i<=cnt;++i) printf("%d^%d\n",pri[i],count[i]);
}

至于 \(Pollard\ Rho\)算法 ，戳这里。

约数

定义

设 $a,b$ 满足 $a\in\mathbb{N}^+ \,\ b\in\mathbb{N}$ 。若 $\exists \ \ q\in\mathbb{N}$ ，使得 $b = a \times q$ , 那么就说 $b$ 是 $a$ 的倍数， $a$ 是 $b$ 的约数。这种关系记作 $a \mid b$ ，读作" $a$ 整除 $b$"。

算数基本定理的推论

• 在算数基本定理中，若正整数 \(N\) 被唯一分解为 \(N = p_{1}^{c_1} p_{2}^{c_2} \cdots p_{m}^{c_m}\) ，其中 $c_i \in\mathbb{N}^+ $， \(p_i\)均为质数，且满足 \(p_1 < p_2 < \cdots <p_m\) ，则 \(N\) 的正约数集合可写为：
  

  \[ \{{p_{1}^{b_1} p_{2}^{b_2} \cdots p_{m}^{b_m}} \} ，其中 0≤b_i≤c_i\]

• \(N\) 的正约数个数为：
  

  \[ (c_1+1) \times (c_2+1) \times \cdots \times (c_m+1) = \prod_{i=1}^{m} {(c_i+1)}\]

• \(N\) 的所有正约数的和为：
  

  \[ (1 + p_1 + p_1^{2} + \cdots +p_1^{c_1} ) \times \cdots \times (1 + p_m + p_m^{2} + \cdots +p_m^{c_m} ) = \sum_{i=1}^{m} (\prod_{j=0}^{c_i} {p_i^j}) \]

• 由等比数列相关知识，上述式子可变为：
  

  \[ \prod_{i=1}^{m} (\frac{1 - p_i^{c_i+1}}{1 - p_i}) \]

求正约数集合

1. 试除法（求$N$的正约数集合）

• 若 \(d≥ \sqrt{N}\) 是 \(N\) 的约数，则 \(\frac{N}{d} ≤ \sqrt{N}\) 也是 \(N\) 的约数。（当 \(\sqrt{N} \in\mathbb{N}^+\)，需特判一下）

• 所以，只需线性扫描一遍 \(d = 1\) ~ \(\sqrt{N}\) ，复杂度为 \(O(\sqrt{N})\) 。

• 推论：一个整数 \(N\) 的约数个数上界为 \(2\sqrt{N}\)。

• Code：

const int N=100005;
int factor[N],cnt,n;
inline void factor_Search(int n)
{
    for(int i=1;i*i<=n;++i)
    {
        if(n%i==0)
        {
            factor[++cnt]=i;
            if(i*i!=n) factor[++cnt]=n/i;
        }
    }
    for(int i=1;i<=cnt;++i) printf("%d ",factor[i]);
}

2. 倍数法（求 $1$ ~ $N$ 的每个数的正约数集合）

• 对于每个整数 \(d \in \left[1,N \right]\) ， \(1\) ~ \(N\) 中以 \(d\) 为约数的数就是 \(d\) 的倍数： \(2d\)、\(3d\)、 \(\cdots\) 、\(\left \lfloor \frac{N}{d} \right \rfloor * d\)。

• 时间复杂度：\(O(N + \frac{N}{2} + \frac{N}{3} + \cdots + \frac{N}{N})\) = \(\cdots\) （证明有点多，不想写） = \(O(N \times ( \ln(N+1) + r ))\) （ \(r\) 即为著名的欧拉常数， \(r \approx 0.5772156649\) ） = \(O(N\log N)\) 。

• Code：

const int N=1e6+5;
vector<int>factor[N];
for(int i=1;i<=n;++i)
    for(int j=1;j*i<=n;++j)
        factor[i*j].push_back(i);
for(int i=1;i<=n;++i)
{
    for(int j=0;j<factor[i].size();++j) printf("%d ",factor[i][j]);
    putchar('\n');
}

最大公约数

定义

若自然数 $d$ 同时是自然数 $a$ 、$b$ 的约数，则称 $d$ 是 $a$、$b$ 的公约数。其中，$a$ 、$b$ 的公约数中最大的一个，称作 $a$ 和 $b$ 的最大公约数，记作 $\gcd(a,b)$。

同理，若自然数 $m$ 同时是自然数 $a$ 、$b$ 的倍数，则称 $m$ 是 $a$、$b$ 的公倍数。其中，$a$ 、$b$ 的公倍数中最小的一个，称作 $a$ 和 $b$ 的最小公倍数，记作 $lcm(a,b)$。

几个定理：

1. \[ \forall a,b \in\mathbb{N} \quad \gcd(a,b) \times lcm(a,b) = a \times b \]

2. \[\forall a,b,c \in\mathbb{N} \quad \gcd(a,lcm(b,c)) = lcm(\gcd(a,b),\gcd(a,c)) \]

3. \[\forall a,b,c \in\mathbb{N} \quad lcm(a,\gcd(b,c)) = \gcd(lcm(a,b),lcm(a,c)) \]
   

   这里只简要证明 \(1\)

• 设 \(d = \gcd(a,b)\ ,a_0 = \frac{a}{d}\ ,b_0 = \frac{b}{d}\) 。由 \(gcd\) 的定义，有 \(\gcd(a_0,b_0) = 1\) ；由 \(lcm\) 的定义，有 \(lcm(a,b) = a_0 \times b_0\) 。

• $\Rightarrow  $ \(lcm(a,b) = lcm(a_0 \times d,b_0 \times d) = lcm(a_0,b_0) \times d = a_0 \times b_0 \times d = \frac{a \times b}{d} = \frac{a \times b}{\gcd(a,b)}\) 。

gcd的求法

1. 九章算术 $\cdot$ 更相减损术

• \(\forall a,b \in\mathbb{N} \ ,a≥b\) ，有 \(gcd(a,b) = gcd(b,a-b) = gcd(a,a-b)\)。

• \(\forall a,b \in\mathbb{N}\) ， 有 \(\gcd(2a,2b) = \gcd(a,b)\) 。

由 $gcd$ 的定义，第二条显然成立。这里只证明第一条。

• 设 \(d = \gcd(a,b)\ ,a = d \times k_1\ ,b = d \times k_2\)，则 \(a-b = (k_1 - k_2) \times d\)，由\(gcd\)定义得：\(\gcd(k_1,k_2) = 1\)。

• 先假设 \(\gcd(k_1 - k_2,k_2)>1\)，设 \(k_1 = p \times m\ ,k_2 = q \times m\)（\(p,q,m \in\mathbb{Z}\) 且 \(p,q,m >1\)），则有 \(k1 = (p - q) \times m\) 。

• $\Rightarrow  $ \(\gcd(k_1,k_2) = m\) 与 \(\gcd(k_1,k_2) = 1\)矛盾。故假设不成立，故 \(\gcd(k_1 - k_2,k_2) = 1\)。

• $\therefore $ 由 \(gcd\) 定义得 \(\gcd(b,b - a) = d =\gcd(a,b)\)。

2. 欧几里得算法（辗转相除法）

• \[\forall a,b \in\mathbb{N}\ ,b \ne 0 \qquad \gcd(a,b) = \gcd(b,a\%b)\]

证明

• 若 \(a<b\)，则 \(\gcd(b,a\%b) = \gcd(b,a) = \gcd(a,b)\)。

• 若 \(a≥b\) ，设 \(a = q \times b + r\) ，其中 \(0≤ r <b\) 。此时显然有 \(r = a \% b\)。

• 对于 \(a,b\) 的任意公约数 \(d\) ，$\because d \mid a  , d \mid q \times b \quad \therefore d \mid (a - q \times b) \Rightarrow   d \mid r  $ \(\Rightarrow d\) 也是 \(b,r\) 的公约数

• 反之亦成立。故 \(a,b\) 的公约数集合与 \(b,a \% b\) 的公约数集合相同。\(\Rightarrow \gcd(a,b) = \gcd(b,a \% b)\)。

简易代码：

#define ll long long
template<typename TP>ll Gcd(TP a,TP b) {return !b?a:Gcd(b,a%b);}

总结：欧几里得算法复杂度为 $O(log(a+b))$ ，故很常用。不过如果涉及到高精度计算，还是用更相减损术吧！

互质与欧拉函数

定义

$\forall a,b \in\mathbb{N}$ ，若 $\gcd(a,b) = 1$ ，则称 $a,b$ 互质，记为 $a\ \bot\ b$ ，同时：

• 如果数域是 \(\mathbb {N^{+}}\) ，那么 \(1\) 与所有正整数互质。

• 如果数域是 \(\mathbb {Z}\) ，那么 \(1\) 和 \(-1\) 与所有整数互素，而且它们是唯一与 \(0\) 互素的整数。

对于三个或三个以上的整数互质，有两种情况：

• 这些整数的最大公约数是 \(1\)，我们直接称这些整数互素，也称为整集互素。以 \(\{ {6,8,9} \}\) 为例：

  \(\gcd(6,8,9) = \gcd(\gcd(6,8),9) = \gcd(2,9) = 1\)

• 这些整数是两两互质的。以 \(\{ {7,8,9} \}\) 为例：

  \(\gcd(7,8) = \gcd(8,9) = \gcd(7,9) = 1\)

  \(\Rightarrow \gcd(7,8,9) = \gcd(7,\gcd(8,9)) = \gcd(8,\gcd(7,9)) = \gcd(9,\gcd(7,8)) = 1\)

注：两两互素是较为严格的互素，如果一个整数集合是两两互素的，它也必定是整集互素，但是整集互素不必然是两两互素。

欧拉函数

注：以下内容主要摘自蓝书

1. 定义：

• $ \left[1,N\right] $ 中与 \(N\) 互质的数的个数被称为欧拉函数，记作 \(\varphi(N)\) 。

• 若在算数基本定理中， \(N = p_1^{c_1}p_2^{c_2} \cdots p_m^{c_m}\) ，则：
  

  \[ \varphi(N) = N \times \frac{p_1-1}{p_1} \times \frac{p_1-1}{p_1} \times \cdots \times \frac{p_1-1}{p_1} = N \times \prod\limits_{p_i \mid N} (1 - \frac{1}{p_i})\]

• 证明：设 \(p\ ,q\) 是 \(N\) 的质因子，$ \left[1,N\right] $ 中 \(p\) 的倍数有 \(p\ ,2p\ ,3p\ ,\cdots \ ,\left \lfloor \frac{N}{p} \right \rfloor \times p\)，共 \(\left \lfloor \frac{N}{p} \right \rfloor\) 个。同理， \(q\) 也是如此。如果把这 $\left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{q} \right \rfloor $ 个数去掉，那么 \(p \times q\) 的倍数就被排除了两次，需要加回来一次。因此，$ \left[1,N\right] $中不与 \(N\) 含共同质因子 \(p\) 或 \(q\) 的个数为：

  \[N - \frac{N}{p} - \frac{N}{q} + \frac{N}{pq} = N \times (1 - \frac{N}{p} - \frac{N}{q} + \frac{N}{pq}) = N (1 - \frac{1}{p}) (1 - \frac{1}{q})\]

  类似的，可以对 \(N\) 的所有质因子使用上述方法，即可得到 \(\varphi(N)\) 的值。

2. 相关性质：

• \(\forall N > 1\quad , \sum\limits_{i = 1\ ,\gcd(i,N) = 1}^{N}(i) = N \times \frac{\varphi(N)}{2}\)

• 若 \(\gcd(a,b) = 1\)，则 \(\varphi(ab) = \varphi(a)\varphi(b)\)（至于积性函数，以后再作详细介绍）

• 设 \(p\) 是质数，若 \(p \mid n\) 且 \(p^2 \mid n\) ，则 \(\varphi(N) = \varphi(\frac{N}{p}) \times p\)

• 设 \(p\) 是质数，若 \(p \mid n\) 但 \(p^2 \nmid n\) ，则 \(\varphi(N) = \varphi(\frac{N}{p}) \times (p-1)\)

• \(\sum_{d \mid N}\varphi(d) = N\)

  证明略 \(\cdots\)

3. $\varphi$ 的求法：

⑴ 单独求 \(\varphi(N)\)

根据 \(\varphi\) 的公式，我们只需在分解质因数的同时即可顺便求出 \(\varphi\) 。复杂度显而易见为 \(O(\sqrt{N})\)。

Code：

inline int phi(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;++i)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

⑵ 求 \(\left[1,N\right]\) 中每个数的 \(\varphi\)

• 利用 \(Eratosthenes\) 筛法，根据公式，可以在 \(O(NlogN)\) 的时间内求出。

Code：

const int N=100005;
int phi[N];
inline void Euler(int n)
{
    for(int i=1;i<=n;++i) phi[i]=i;
    for(int i=2;i<=n;++i)
        if(phi[i]==i)
            for(int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i-1);
}

• 利用性质 \(3\ ,4\) 和线性筛，可在 \(O(N)\) 时间内求出。

Code：

bitset<10000005>vis;
int pri[N],phi[N],cnt;
inline Euler(int n)
{
    phi[1]=1;
    F1(i,2,n)
    {
        if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;
        for(rg j=1;j<=cnt && pri[j]*i<=n;++j)
        {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0)
            {
                phi[pri[j]*i]=pri[j]*phi[i];
                break;
            }
            else phi[pri[j]*i]=(pri[j]-1)*phi[i];
        }
    }
}