数论基础

1.最大公因数（ $gcd$gcd）:

解法：辗转相除法：

原理： $gcd(a,b)=gcd(b,a\%b)$gcd(a,b)=gcd(b,a%b)

证明：

假设 $a>b$a>b ，那么 $a$a 可以表示成 $a=k\ast b+r$a=k∗b+r（ $a，b，k，r$a，b，k，r 皆为正整数，且 r<b），
则 $r=a\%b$r=a%b。
假设 $d$d 是 $a,b$a,b 的一个公约数，记作 $d\mid a,d\mid b$d∣a,d∣b。
而 $r=a-k\ast b$r=a−k∗b，两边同时除以 $d$d，得： $\frac{r}{d}=\frac{a}{d}-\frac{k\ast b}{d}=m$dr​=da​−dk∗b​=m；
由等式右边可知 $m$m 为整数，因此 $d\mid r$d∣r；
因此 $d$d 也是 $b\hspace{0.25em} ,\hspace{0.25em} a\%b$b,a%b 的公约数；
假设 $d$d 是 $b,a\%b$b,a%b 的公约数, 则 $d\mid b,d\mid (a-k\ast b)$d∣b,d∣(a−k∗b) 是一个整数，进而 $d\mid a$d∣a 。
因此 $d$d 也是 $a,b$a,b 的公约数；
因此 $(a,b)$(a,b) 和 $(b,a\%b)$(b,a%b) 的公约数是一样的，其最大公约数也必然相等，
得证。

代码：

int _gcd(int x,int y)
{
    return y?_gcd(y,x%y):x;
}

也可以直接利用 $\text{algorithm}$algorithm 库中的函数 $\text{\_\_gcd(x,y)}$__gcd(x,y)。

2.最小公倍数（ $lcm$lcm）：

两个数 $a,b$a,b 的最小公倍数：

ans=a/gcd(a,b)*b;//注意先除后乘，否则容易溢出

3.唯一分解定理：

定义：

任意一个大于 $0$0 的正整数都能被表示成若干个素数的乘积且表示方法是唯一的。
即 $n=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}$n=p1a1​​∗p2a2​​∗...∗pkak​​

应用：

(1) $gcd$gcd 为 $a,b$a,b 两数所有相同质因子最小指数幂的乘积。
(2) $lcm$lcm 为 $a,b$a,b 两数所有的质因子的最大指数幂的乘积。
可以拓展到多个数。
(3)一个数因子个数：
$n=(1+a_1)\ast (1+a_2)\ast (1+a_3)\ast ...\ast (1+a_k)$n=(1+a1​)∗(1+a2​)∗(1+a3​)∗...∗(1+ak​)
(4)一个数的所有因子和：
$n=\prod _{i=1}^k\sum _{j=0}^{a_i}{p}_i^j=(1+p_1^1+p_1^2+...+p_1^{a_1})\ast (1+p_2^1+p_2^2+...+p_2^{a_2})\ast ...(1+p_k^1+p_k^2+...+p_k^{a_k})$n=i=1∏k​j=0∑ai​​pij​=(1+p11​+p12​+...+p1a1​​)∗(1+p21​+p22​+...+p2a2​​)∗...(1+pk1​+pk2​+...+pkak​​)

质因子分解代码：

复杂度： $O\left(n^{\frac{1}{2}}\right)$O(n21​)

//注意初始化
cnt=0;
for(int i=2;i*i<=num;i++)//sqrt(n)的复杂度
{
    if(num%i==0)
    {
        factor[++cnt]=i;//存质因子
        while(tn%i==0)
        {
            e[cnt]++;//质因子的幂
            num/=i;
        }
   }
}
if(num>1)//不能省略！
{
     factor[++cnt]=num;
     e[cnt]++;
}

还可以预处理出素数表来加快分解速度。
大整数质因子分解：Pollard Rho因数分解

4.素数筛法：

埃氏筛：

实现：

  首先将 $2$2 到 $n$n 范围内的整数写下来，其中 $2$2 是最小的素数。将所有的 $2$2 的倍数筛去，剩下的最小的数字就是 $3$3 ，它不能被更小的数整除，所以 $3$3 是素数。再将所有的 $3$3 的倍数划去……以此类推。如果剩余的最小的数是 $m$m，那么 $m$m 就是素数。然后将所有 $m$m 的倍数划去，像这样反复操作，就能依次枚举 $n$n 以内的素数。
时间复杂度： $O\left(nloglogn\right)$O(nloglogn)

代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
vector<int>prime;//存素数
bool vis[N];//vis=false为素数
void Sieve()
{
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime.pb(i);
            for(int j=i;j<N;j+=i)//建议用加法
            //for(int j=1;j*i<N;j++)
                vis[j]=1;
        }
    }
}
int main()
{
    Sieve();
    for(int i=0;i<10;i++)
        cout<<prime[i]<<endl;
    return 0;
}

不足：一个数可能会被不同的质因子筛多次，造成时间的浪费。

欧拉筛（线性筛）：

保证了每个合数只会被它的最小素因子筛掉，就把复杂度降到了 $O\left(N\right)$O(N)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool vis[N];//标记非素数
vector<int>prime;//保存素数
void euler()
{
    prime.clear();
    memset(vis,0,sizeof(vis));
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
            prime.push_back(i);
        for(int j=0;j<prime.size()&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)//重点
                break;
        }
    }
}
int main()
{
    euler();
    return 0;
}

应用：

求积性函数。

5.快速幂：

定义：

要求 $a^b$ab，朴素做法是把 $a$a 连乘 $b$b 次。时间复杂度为 $O\left(n\right)$O(n)。
把 $b$b 拆成二进制，该二进制数第 $i$i 位的权为 $2^i$2i。
所以 $a^b=a^{2^k+...+2^0}$ab=a2k+...+20

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll power(ll a,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int main()
{
    cout<<power(1LL*100,1LL*100,1LL*11)<<endl;
    return 0;
}

6.逆元（乘法逆元）：

定义：

若 $a\ast x=1\left(mod\hspace{0.25em} p\right)$a∗x=1(modp)，则 $x$x 称为 $a$a 在模 $p$p 意义下的逆元，即 $x=inv\left(a\right)$x=inv(a)。
$(a+b)\%p=(a\%p+b\%p)\%p$(a+b)%p=(a%p+b%p)%p （√）
$(a-b)\%p=(a\%p-b\%p)\%p$(a−b)%p=(a%p−b%p)%p （√）
$(a\ast b)\%p=(a\%p\ast b\%p)\%p$(a∗b)%p=(a%p∗b%p)%p （√）
$\left(a/b\right)\%p=\left(a\%p/b\%p\right)\%p$(a/b)%p=(a%p/b%p)%p （ $\times$×）

求法：

(1)费马小定理：

当 $p$p 为素数， $a$a 为正整数，且 $a,p$a,p 互质时，有
$a^{(p-1)}=1\left(mod\hspace{0.25em} p\right)$a(p−1)=1(modp)
故 $inv\left(a\right)=a^{p-2}$inv(a)=ap−2。
用快速幂取模求解即可。
复杂度： $O\left(logn\right)$O(logn)

(2)拓展欧几里得：

$a\ast x=1\left(mod\hspace{0.25em} p\right)⟹a\ast x+p\ast y=1$a∗x=1(modp)⟹a∗x+p∗y=1
转化和求 $x$x 的最小正整数解（转化为 $[0,p)$[0,p) 内即可）。
要求满足 $gcd(a,p)=1$gcd(a,p)=1，否则方程无解，逆元不存在。
复杂度： $O\left(logn\right)$O(logn)

(3)递推求逆元：

求 $[1,p)$[1,p) 内的逆元。
复杂度： $O\left(n\right)$O(n)
公式： $inv\left[i\right]=(p-p/i)\ast inv\left[p\%i\right]\%p$inv[i]=(p−p/i)∗inv[p%i]%p
推导：
设 $p=k\ast i+r$p=k∗i+r，有
$k\ast i+r=0\left(mod\hspace{0.25em} p\right)$k∗i+r=0(modp)
即 $r=-k\ast i\left(mod\hspace{0.25em} p\right)$r=−k∗i(modp)
两边同时除以 $r\ast i$r∗i，有 $inv\left[i\right]=-k\ast inv\left[r\right]\left(mod\hspace{0.25em} p\right)$inv[i]=−k∗inv[r](modp)
将 $k,r$k,r 替换掉， $inv\left[i\right]=(-k)\ast inv\left[p\%i\right]\%p$inv[i]=(−k)∗inv[p%i]%p
因为 $(-k)\%p=(p-k)\%p$(−k)%p=(p−k)%p，所以有 $inv\left[i\right]=(p-p/i)\ast inv\left[p\%i\right]\%p$inv[i]=(p−p/i)∗inv[p%i]%p
初始化 $inv\left[1\right]=1$inv[1]=1，即可递推求出所有逆元。
补充： $[1,p)$[1,p) 内的所有数的逆元对于 $[1,p)$[1,p) 内的所有数。
代码：

void get_inv()
{
    inv[1]=1;
    for(int i=2;i<p;i++)
        inv[i]=(p-p/i)*inv[p%i]%p;
}

7.素数分布定理：

定义：

对正整数 $x$x，记 $\pi \left(x\right)$π(x) 为不大于 $x$x 的素数个数。
x→∞lim​x/ln(x)π(x)​=1

大致分布表：

例题：2019 ICPC Asia Xuzhou Regional C. <3 numbers

8.组合数：

组合数公式：

$\begin{array}{cc}C(n,m)=\frac{n\ast (n-1)\ast (n-2)\ast ..\ast (n-m+1)}{m!}=\frac{n!}{(n-m)!\ast m!}& \text{(1)}\end{array}$C(n,m)=m!n∗(n−1)∗(n−2)∗..∗(n−m+1)​=(n−m)!∗m!n!​(1)

$\begin{array}{cc}C(n,m)=C(n,n-m)& \text{(2)}\end{array}$C(n,m)=C(n,n−m)(2)

线性递推：

$C(n,k)=C(n,k-1)\ast \frac{(n-k+1)}{k}$C(n,k)=C(n,k−1)∗k(n−k+1)​

杨辉三角：

递推式： $C(n,m)=C(n-1,m)+C(n-1,m-1)$C(n,m)=C(n−1,m)+C(n−1,m−1)
复杂度： $O\left(n^2\right)$O(n2)

代码：

void init()
{
    for(int i=0;i<=n;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
}

二项式定理：

公式：

$(x+y{)}^n=C(n,0)\ast x^0\ast y^n+C(n,1)\ast x^1\ast y^{(n-1)}+...+C(n,n)\ast x^n\ast y^0$(x+y)n=C(n,0)∗x0∗yn+C(n,1)∗x1∗y(n−1)+...+C(n,n)∗xn∗y0

9.位运算：

(1)判断 $n$n 是否为 $2$2 的整数次幂： n&(n−1)==0；
(2)找到 $n$n 中最低的 $1$1 位：n&(~(n-1))；
(3) a+b=a⨁b+2∗(a&b)，异或是不进位的加法；
(4)或( $\mid$∣) 可以用来判断子集；

10.同余方程：

一元线性同余方程：

欧几里得算法：

$gcd(a,b)=gcd(b,a\%b)$gcd(a,b)=gcd(b,a%b)

拓展欧几里得：

方程 $ax+by=gcd(a,b)$ax+by=gcd(a,b)，必然有解。
证明：
当 $b=0$b=0 时，有 $gcd(a,b)=a$gcd(a,b)=a， $\{\begin{array}{c}{x}_0=1\\ y_0=0\end{array}${x0​=1y0​=0​   为一组解。

当 $b\hspace{0.25em} !=0$b!=0时，
$a\ast x_1+b\ast y_1=gcd(a,b)=b\ast x_2+\left(a\%b\right)\ast y_2$a∗x1​+b∗y1​=gcd(a,b)=b∗x2​+(a%b)∗y2​
$\Rightarrow a\ast x_1+b\ast y_1=b\ast x_2+(a-(a/b)\ast b)\ast y_2$⇒a∗x1​+b∗y1​=b∗x2​+(a−(a/b)∗b)∗y2​
$\Rightarrow a\ast x_1+b\ast y_1=a\ast y_2+b\ast (x_2-(a/b)\ast y_2)$⇒a∗x1​+b∗y1​=a∗y2​+b∗(x2​−(a/b)∗y2​)

所以： $\{\begin{array}{c}{x}_1=y_2\\ y_1=x_2-\left(a/b\right)\ast y_2\end{array}${x1​=y2​y1​=x2​−(a/b)∗y2​​

据此，一直向下递归，直到到达边界 $b=0$b=0。然后回溯，利用不同方程的解的关系求解。

三种常见应用：

1.求解不定方程：

对于 $ax+by=c$ax+by=c 的不定方程，
$\{\begin{array}{c}c\%gcd(a,b)!=0,无整数解\\ c\%gcd(a,b)=0,有整数解\end{array}${c%gcd(a,b)!=0,无整数解c%gcd(a,b)=0,有整数解​
当 $c\%gcd(a,b)=0$c%gcd(a,b)=0 时，
先求解方程 $a\ast x+b\ast y=gcd(a,b)$a∗x+b∗y=gcd(a,b)，然后把解同时乘以 $c/gcd(a,b)$c/gcd(a,b)，即可得出原方程的解。
假设 $x_0,y_0$x0​,y0​ 为方程的一组解，
则通解：

$\{\begin{array}{c}x=x_0+b/gcd(a,b)\ast k\\ y=y_0-a/gcd(a,b)\ast k\end{array}${x=x0​+b/gcd(a,b)∗ky=y0​−a/gcd(a,b)∗k​

把通解代入原方程，可以发现恒成立。

$x$x 的最小正整数解： $x=(x\%b+b)\%b$x=(x%b+b)%b

注意：在一些问题中 $a,b$a,b 等系数可能为负。

2.求解模线性方程（线性同余方程）：

可以转化为求解不定方程。

3.求解模的逆元：

转化为求解不定方程。

拓展欧几里得解不定方程代码：

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll ans=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return ans;
}
ll cal(ll a,ll b,ll c)
{
    ll x,y;
    ll gcd=exgcd(a,b,x,y);
    if(c%gcd)
        return -1;
    x=c/gcd*x;
    x=(x%b+b)%b;
    return x;
}

11.中国剩余定理：

一元线性同余方程组：
$x=a_1\left(mod{m}_1\right)$x=a1​(mod m1​)
$x=a_2\left(mod{m}_2\right)$x=a2​(mod m2​)
$x=a_3\left(mod{m}_3\right)$x=a3​(mod m3​)
$x=a_4\left(mod{m}_4\right)$x=a4​(mod m4​)
…
$x=a_n\left(mod{m}_n\right)$x=an​(mod mn​)
其中 $m_1,m_2,...,m_n$m1​,m2​,...,mn​ 两两互质，对于任意的 $a_1,a_2,...,a_n$a1​,a2​,...,an​ 方程组有解。
可以把解构造成如下形式：
$x=p_1+p_2+p_3+...+p_n$x=p1​+p2​+p3​+...+pn​，

其中 $p_1\%m_1=a_1,...,p_n\%m_n=a_n$p1​%m1​=a1​ ,..., pn​%mn​=an​，且 $p_i\%{\prod }_{j=1,j\ne i}^n{m}_j=0$pi​%∏j=1,j​=in​mj​=0，
那么这样的 $x$x 一定满足条件。
以求 $p_1$p1​ 为例：
假设 $tm={\prod }_{i=1,i\ne 1}^n{m}_i$tm=∏i=1,i​=1n​mi​，