线性筛(欧拉筛)

• 我们会发现，埃氏筛仍然会有一些地方，重复标记合数。比如，12 同时被 2 和 3 标记。其根本原因就是我们没有确定出唯一的产生 12 的方式。

• 那么我们是否能对每一个合数，通过某种顺序，确定产生这种合数的唯一方式呢？

• 想想我们学过的跟 “唯一”“确定”有关的定理——算术基本定理（唯一分解定理），呃呃现在没学无所谓下面很快会提到，我们可以想办法把一个合数通过类似“分解质因数”的办法把它们“拆”成唯一的分解形式。比如，我们让 12 只能通过 \(3 \times 2 \times 2\) 得到，而不通过其他方式得到。而这个唯一分解形式的关键就在于：质因子！！！那么我们就可以创造一种类似于逆向分解质因数的办法，来使得每个合数产生的方式是唯一的。

• 基本思想：从小到大枚举 i ，如果 i 没被标记过，就标记为质数。每次枚举不大于 i 的质数 x ，将 \(x \times i\) 标记为合数，然后如果 x 不是 \(x \times i\) 最小的质数，那么break即可。

• 两种实现方法：

  • 第一种：用 vis[] 表示是否被标记为质数。

    判断是否为最小质因子的方法：if(!(i%p[j]))break;原理：感觉模板题题解的一部分地方说的挺好的。这里截过来：

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

• 第二种：用 vis[] 存储最小质因子。对于一个数 x 的 vis，若vis[x]

for(int i=2;i<=n;i++)
    {
        if(vis[i]==0){vis[i]=i;p[++cnt]=i;}
        for(int j=1;j<=cnt&&i*p[j]<=n;j++)
        {
            if(p[j]>v[i])break;
            vis[i*p[j]]=p[j];
        }
    }

• 时间复杂度：由于每个质数只会被它的最小质因子筛一次，所以时间复杂度 \(O(n)\)。

质因数分解

唯一分解定理（算数基本定理）

• 任何一个大于 1 的正整数都可以唯一分解为有限个质数的乘积，可写作：

• \(N={p_1}^{c_1} {p_2}^{c_2}…{p_m}^{c_m}\)

• 其中 \(c_i\) 都是正整数，\(p_i\) 都是质数，且满足 \(p_1。

试除法

这个很简单，首先根据质数的判定是从 \(1-\sqrt n\) 来扫，那么我们也只需要试除 \(1-\sqrt n\) 的质数，即可完成对 n 的质因数分解。

如何试除从 \(1-\sqrt n\) 的质数呢？我们只需要从 1 枚举到 \(\sqrt n\) ，每次遇到一个能被 n 整除的数就不断对 n/=i，直到 n%i 不为 0 即可。

为什么这么做是对的呢？因为一个合数的影子一定在扫描到这个合数之前就从 n 中被除去了，所以上述过程中能整除 n 的一定是质数，多次 n/=i 不仅是为了排除之后 i 的倍数对 n 的干扰，还能够起到累计计算 i 的个数的作用。

时间复杂度：显而易见的 \(O(\sqrt n)\)

代码实现：

for(int i=2;i*i<=n;i++)
{
      if(n%i==0)
      {
           p[++cnt]=i;c[cnt]=0;
           while(n%i==0)n/=i,c[cnt]++;
      }
}

if(n>1) p[++cnt]=n,c[cnt]=1;//注意一下这里，如果这时候 n 还没被除到1，则说明 n 是质数。

• 同余

这块有好多%意义下的运算，由于我太菜，这块很迷惑，所以先把这块总结一下吧。

定义

若整数 a 和整数 b 除以正整数 m 的余数相同，则称 a，b 模 m 同余，记为 \(a \equiv b\pmod {m}\)。

同余系与剩余系

同余类：对于 $ {\forall} a \in [0,m-1]$,集合 \(\{a+km\}(k \in \mathbb Z)\)的所有数模 \(m\) 同余,余数都是 \(a\)，该集合称为一个模 \(m\) 的同余类，简记为 \(\overline a\) 。

完全剩余系：\(m\) 个模 \(m\) 的同余类构成 \(m\) 的完全剩余系，分别是 \(\overline 0\)，\(\overline 1\)，\(\overline 2\)，…，\(\overline {m-1}\) 。

简化剩余系：\(1-m\) 中与 \(m\) 互质的数代表的同余类共同构成 \(m\) 的简化同余系，共有 \(m\) 个。e.g. 模 10 的简化剩余系为 \(\{\overline 1,\overline 3,\overline 7,\overline 9\}\)。

一个性质

首先我们要说一个概念：

运算封闭：若从某个非空集合中任选两个元素（同一元素可重复选出），选出的这两个元素通过某种（或几种）运算后的得数仍然是该数集中的元素，那么就说该集合对于这种（或几种）运算是封闭的。

简化剩余系关于模 \(m\) 算法完全封闭。理由：若 \(a,b(1 \le a,b \le m)\) 与 \(m\) 互质，则 \(a \times b\) 也不可能与 \(m\) 含有相同的质因子， 即 \(a \times b\) 也与 \(m\) 互质。而我们知道，如果 \(a\) 与 \(m\) 互质，那么 \(a \bmod b\) 也一定与 \(m\) 互质，所以 \(a \times b \bmod m\) 也与 \(m\) 互质，即 \(a \times b \bmod m\) 也属于 \(m\) 的简化剩余系。

费马小定理

若 \(p\) 是质数，则对于任意整数 \(a\) ，有 $a^p \equiv a\pmod {p} $。

欧拉定理

若正整数 \(a,n\) 互质，则 \(a^{\varphi(n)} \equiv 1\pmod {n}\)，其中 \(\varphi(n)\) 为欧拉函数。

说明：

1. \(\varphi(n)\) 表示的是小于等于 \(n\) 并且和 \(n\) 互质的数。易知：当 \(n\) 为质数，\(\varphi(n)=n-1\)

2. \(a^{\varphi(n)} \equiv 1\pmod {n}\) 表示的是 \(a^{\varphi(n)} \bmod n=1\) 。也就是， \(a^{\varphi(n)} =nk+1(n \in \mathbb Z)\)。

欧拉定理推论

若正整数 \(a,n\) 互质，则对于任意正整数 \(b\)，有 \(a^b \equiv a^{b \bmod \varphi(n)} \pmod n\)。

//感性理解一下（不是正文）a的b次方和 a的b模phi(n) 次方mod n的值是一样的。也就是说，a^b mod n= a^(bmod phi(n))

许多计数类的题目要求我们把答案对一个质数 \(p\) 取模后输出。面对 \(a+b,a-b,a*b\) 这样的算式，可以先把 \(a,b\) 对 \(p\) 取模。面对乘方算式，根据欧拉定理的推论，可以先把底数对 \(p\) 取模，指数对 \(\varphi(n)\) 取模，再计算乘方。

——《算法竞赛进阶指南》

扩展欧几里得算法(exgcd)

扩展欧几里得算法(exgcd)，常用于求解 \(ax+by=\gcd(a,b)\) 一组合法解问题。

求解：

设 \(ax_1+by_1=\gcd(a,b),bx_2+a \bmod b y_2=\gcd(b,a \bmod b)\)。

根据欧几里得定理， \(\gcd(a,b)=\gcd(b,a \bmod b)\)。

\(\therefore\) \(ax_1+by_1=bx_2+a \bmod by_2\)

$\because a \bmod b=a-b \times \biggl\lfloor\frac a b\biggr\rfloor $

\(\therefore ax_1+by_1=bx_2+(a-b \times \biggl\lfloor\frac a b\biggr\rfloor)y_2=bx_2+ay_2-b \biggl\lfloor\frac a b\biggr\rfloor y_2=ay_2+b(x_2- \biggl\lfloor\frac a b\biggr\rfloor y_2)\)

$\because a=a,b=b $

\(\therefore x_1=y_2,y_1=x_2- \biggl\lfloor\frac a b\biggr\rfloor y_2\)

所以只需要将 \(x_2,y_2\) 不断代入递归求解直至 \(\gcd\) 为 0 递归 \(x=1,y=0\) 求解。

代码实现：

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1;y=0;return a;}
    int d=exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-y*(a/b);
    return d;
}

说明：

1. 简述一下上述代码的过程。定义变量 \(d,x_0,y_0\) ，调用 \(d=exgcd(a,b,x_0,y_0)\) 。其中 \(x_0,y_0\) 是通过引用的方式传递的。每次递归 d=exgcd(b,a%b,x,y)，再通过引用的方式每次改变 \(x,y\) 的值。上述程序中求出方程 \(ax+by=\gcd(a,b)\) 的一组特解 \(x_0,y_0\) ,并返回 \(d=\gcd(a,b)\)；

2. 更一般地，对于方程 \(ax+by=c\) ，它有解的充要条件是当且仅当 \(d|c\) 。

证明：

• 充分性：首先根据 exgcd 可知，存在 $(x_0,y_0) $使得 \(ax_0+by_0=d\) ,又 \(d|c\) ,所以 \(c=dk=(ax_0+by_0)k=a(kx_0)+b(ky_0)\) ，所以方程有整数解 \((kx_0,ky_0)\)

• 必要性：因为 \(ax_0+by_0=c\) ，\(d\) 是 \(a,b\) 的最大公约数，所以 \(d|a,d|b\) ，所以 \(d|ax_0+by_0\) ，即 \(d|c\) 。

所以，对于该方程我们可以先求出方程 \(ax+by=d\) 一组特解 \((x_0,y_0)\) ，然后给 \(x_0,y_0\) 同时乘上 \(c/d\) ，即可得到 \(ax+by=c\) 的一组特解 \((c/d)x_0,(c/d)y_0\)。（这里不会的可以手推一下）事实上，将 x,y 代入原方程中就会发现：方程 \(ax+by=c\) 的通解可以表示为：\(x=(c/d)x_0+k(b/d),y=(c/d)y_0-k(a/d)(k\in \mathbb Z)\) 。

乘法逆元

如果一个线性同余方程 \(ax \equiv 1 \pmod b\) 则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}\) 。

求解方法：

1. exgcd：

转化题意可知要求 \(ax=bk+1(k \in \mathbb Z)\) 中的 \(x\) ,也就是 \(ax-bk=1\)。

令 \(-k=y\),则方程 \(ax+by=c\) 与方程 \(ax \equiv c \pmod b\) 等价，所以直接套用上述求 exgcd 的特解的做法即可。

注意：这里只需要求出 \(x\) 即可，不需要求解 \(y\)。

实现代码：

void exgcd(int a,int b,int &x,int &y)//注意这里是void而不是int，因为我们最后要求的不是exgcd，而是里面的 x。
{
    if(b==0){x=1;y=0;return a;}
    int d=exgcd(b,a%b,y,x);//由于要求的直接是 x，就可以在这里直接把x和y swap一下即可。
    y=t-y*(a/b);
}

2. 快速幂法：

线性同余方程

给定整数 \(a,b,m\) ，求一个整数 \(x\) 满足 \(ax \equiv b \pmod m\) ，或者给出无解，因为未知数的指数为 1，所以我们称之为一次同余方程 ，也称线性同余方程。

同样可以转化题意：\(ax \equiv b \pmod m\) 可以转化为 \(ax-bk=m\) ，