基础数论¶

0、前言¶

同余、GCD、LCM、拓展GCD¶

视频链接：

https://www.bilibili.com/video/BV1XR4y1u7Bb/

快速幂和矩阵快速幂和逆元¶

视频链接：

https://www.bilibili.com/video/BV1j3411e7qh/

一、同余¶

1.1 结论¶

\((a+b)\mod\ n=((a\mod\ n)+(b \mod \ n) )\mod\ n\)
\((a-b)\mod\ n =((a\mod\ n) - (b \mod \ n) )\mod \ n\)
\((a \times b) \mod \ n = ((a \mod \ n) \times (b \mod \ n) )\mod \ n\)

二、GCD&LCM¶

2.1 GCD¶

GCD即最大公约数，小学的时候我们就学习了求两数的最大公约数的方法。但是要注意如果有一个数为0的话那么最小公约数就是另一个不为0的数,我们在这里只需要知道GCD是什么东西就行了

2.1.1 更相减损法¶

两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。

2.1.2代码：¶

int gcd_3(int a,int b) {//更相减损法 递归写法 
    if(a == 0)
        return b;
    if(b == 0)
        return a; 
    if(a == b)
        return a;
    if(a > b)
        return gcd_3(a-b,b);
    if(a < b)
        return gcd_3(b-a,a);
}

int gcd_4(int a,int b) {//更相减损法 循环写法 
    if(a == 0)
    　　return b;
    if(b == 0)
    　　return a;
    while(a != b) {
        if(a > b)
            a -= b;
        else
        {
            int t = a;
            a = b - a;
            b = t;
        }
    }
    return a;
}

2.1.3 辗转相除法¶

两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

其实就是把更相减损变得更高级一点（加减运算变乘除运算，提升了一个级别）

但是大整数取模会让一些题极为头疼，所以我们还是要慎重考虑什么时候用更相减损什么时候用辗转相除。

2.1.4 代码¶

int gcd_1(int a,int b){//辗转相除法 循环写法 
    while(b > 0) {
        int t = a%b;
        a = b;
        b = t;
    }
    return a;
}
int gcd_2(int a,int b) {//辗转相除法 递归写法 
    return b?gcd_2(b,a%b) : a;
}

2.2 LCM¶

LCM即最小公倍数，小学的时候也学过，当我们求出GCD的时候，LCM也就出来了，

\[LCM = \frac{a \times b} {GCD(a, b)}\]

2.3 拓展欧几里得¶

2.3.1 前置知识¶

辗转相除法、贝祖定理

辗转相除法就是不断的让较大的数模上较小的数，最后使得其中一个数位0，最后得到答案
贝祖定理：\(ax+by=c,x∈Z*,y∈Z*\) 成立的充要条件是 \(gcd(a,b)|c\)

贝祖定理证明：

设\(s=gcd(a,b)\)，显然\(s|a\)，并且\(s|b\)

又因为\(x，y∈Z\)

所以\(s|ax\),\(s|by\)

显然要使得之前的式子成立，则必须满足\(c\)是\(a\)和\(b\)的公约数的倍数

又因为\(x\)和\(y\)是正整数

所以\(c\)必然是\(a,b\)最大公约数的倍数。

因此，证得该定理成立

当然我这里写的可能只有两元，但是这个定理可以拓展到n元，请大家思考拓展到n元的情况

2.3.2 问题引出¶

求得任意一组解：\(ax+by=1\)

2.3.3 思路¶

很显然，我们能知道如果\(gcd(a,b)!=1\)的话是无解的，所以我们只看\(gcd(a,b)=1\)的情况，通过拓展欧几里得的算法我们可以解决这一类问题

2.3.4 拓展欧几里得算法代码¶

int ex_gcd(int a,int b,int &x,int &y)//返回的值还是GCD(a,b)
{
    if(b==0)//等于0的情况直接返回了
    {
        x=1;
        y=0;
        return a;
    }
    int ans=ex_gcd(b,a%b,x,y);//获得x',y';
    int temp=x;//存储x'
    x=y;//x=y'
    y=temp-(a/b)*x;//y=x'-(a/b)*y'
    return ans;
}

2.3.5 原理证明¶

若\(ax+by=c\)有解，且设\(t = gcd(a,b)\)，则\(c \% t =0\)

①设\(ax+by=t\)

当b等于0时，\(t=a\)，因为\(gcd(a,0)=a\)，则会有\(a\times x = a\)，即\(x=1\)

② 当b不等于0时

设\(ax+by=gcd(a,b)\) ---Ⅰ

我们可以推出下一层的状态：\(bx'+(a\%b)y'=gcd(b,a\%b)\) --- Ⅱ

又因为\(gcd(b,a\%b)=gcd(a,b)\) --- Ⅲ

所以由Ⅰ、Ⅱ、Ⅲ可得：\(ax+by=bx'+(a\%b)y'\) ---Ⅴ

又因为\(a\%b = a - \left \lfloor \frac{a}{b} \right \rfloor \times b\) --- Ⅵ

所以由Ⅴ、Ⅵ可得：\(ax + by = a*y' + b\times (x'- \left \lfloor \frac{a}{b} \right \rfloor \times y')\)

所以可以得到：\(x = y',y = x'- \left \lfloor \frac{a}{b} \right \rfloor \times y'\)

三、唯一分解定理¶

3.1 理论¶

正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。

3.2习题¶

http://120.78.128.11/Challenge.jsp#B213

四、素数三大筛¶

4.1 朴素素数筛¶

4.1.1 原理¶

地球人都知道一个合数A的因子肯定是小于等于\(\sqrt{A}\)的，那么我们就能得到朴素素数筛的方法遍历查找到\(\sqrt{A}\)即可，复杂度\(O(\sqrt{N})\)

4.1.2 代码¶

bool is_prime(int x) {
    if(x == 0 || x == 1)
    return false;
    for(int i = 2; i*i <= x; ++i) {//这里用乘法是为了避免开根号的精度误差
        if(x % i == 0)//如果找到了因子，那么该数就不是质数
            return false;
    }
    return true;
}

4.2 埃式筛¶

4.2.1 原理¶

埃式筛的原理就是通过对已知的质数进行加倍操作，我们就能得到这个质数的大于2的整数倍数都是合数(因子就是该倍数)，这样通过筛选N范围以内的质数就能得到所有的质数，总体复杂度：\(O(nloglogn)\)

4.2.2 代码¶

/*
    作者:Mangata
    埃式筛模板     
*/
//时间复杂度 :O(n*log(log(n))) 
#include<cstdio>
#include<algorithm>
#include<cstring>

const int N = 10000005;
bool vis[N] = {true,true};//初始化 

int main()
{
    int n,x;//离线处理 
    for(int i = 2; i*i <= N; ++i) {
        if (!vis[i]) {
        for(int j = i*2; j <= N; j += i) //把素数的倍数筛掉 
            vis[j] = true;        
        }
    }
    while(~scanf("%d",&x)) {
    if (vis[x])
        puts("No");
    else
        puts("Yes");
    }
    return 0;
}

4.3 欧拉筛¶

4.3.1 原理¶

欧拉筛的思想和埃式筛一样，都是通过对质数的倍数进行筛选，但是有一点不同的是我们在对质数的倍数都进行标记的时候，这里我们其实是重复操作了的，而欧拉筛就能避免重复筛选，让每个合数只被它的最小质因子筛选一次，以达到\(0(N)\)的时间复杂度。

核心操作体现在：if (i % prime[j] == 0) break;

前置知识：任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了

简单证明：

当\(i\%prime[j] == 0\)时，那么就有\(k \times prime[j] = i;\)
设\(i\times prime[j + 1] = X\)(一个未知任意合数)
则：\(i \times prime[j+1] = prime[j] \times k \times prime[j+1] = X\)
又∵ \(prime[j + 1] > prime[j]\)
∴\(prime[j + 1] \times k \ >\ prime[j] \times k\)
∴ \(prime[j+1] \times (k \times prime[j]) = x = i \times prime[j+1]\)
所以可得，\(i \times prime[j+1]\)必然会在以后被\(prime[j]\)的\(k \times prime[j + 1]\)倍数删掉
后面的数字同理

4.3.2 代码¶

/*
    作者:Mangata
    欧拉筛模板     
*/
//时间复杂度为  O(n) 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>

const int N = 10000005; 
int prime[N];
bool vis[N];

void get_prime() {
    memset(vis,true,sizeof vis);
    memset(prime,0,sizeof prime);
    vis[0] = vis[1] = false;
    for(int i = 2; i <= N; ++i) {
        if (vis[i]) {
            prime[++prime[0]] = i;
        }
        for(int j = 1;j <= prime[0] && i * prime[j] <= N; ++j) {
            vis[i * prime[j]] = false;
            if (i % prime[j] == 0) //避免重复筛选               
                break;
        }
    }
}

int main()
{
    int n;
    get_prime();
    while(~scanf("%d",&n)) {
        if (vis[n])
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

4.4 拓展：米勒罗宾¶

对比较大的质数进行一个检测（有一定随机性）

五、矩阵运算¶

5.1 矩阵加减法¶

直接对应位置相加减即可

\[\begin{bmatrix} 4 & 3 \\ 9 & 9 \end{bmatrix} + \begin{bmatrix} 1 & 3 \\ 1 & 4 \end{bmatrix}= \begin{bmatrix} 5 & 6 \\ 10 & 13 \end{bmatrix}\]

\[\begin{bmatrix} 4 & 3 \\ 9 & 9 \end{bmatrix} -\begin{bmatrix} 1 & 3 \\ 1 & 4 \end{bmatrix} =\begin{bmatrix} 3 & 0 \\ 8 & 5 \end{bmatrix}\]

5.2 矩阵乘法¶

矩阵乘法就是\(A\)矩阵的第\(i\) 行和\(B\)矩阵的第\(j\) 列进行乘法运算，并作为结果矩阵C的\(C[i][j]\) 元素

\[\begin{bmatrix} 4 & 3 \\ 9 & 9 \end{bmatrix} \times \begin{bmatrix} 1 & 3 \\ 1 & 4 \end{bmatrix} =\begin{bmatrix} 4 \times 1 + 3\times1 & 4 \times 3 + 3\times 4 \\ 9 \times 1 + 9 \times 1 & 9 \times 3 + 9 \times 4 \end{bmatrix} =\begin{bmatrix} 7 & 24 \\ 18 & 63 \end{bmatrix} \]

5.3 代码¶

#include<bits/stdc++.h>
using namespace std;
#define N 100
struct Matrix{
    int n,m;
    int mp[N][N];
    void init(int n,int m) {
        this->n = n;
        this->m = m;
    }
};

Matrix add(Matrix L,Matrix R) {//加法
    if(L.n != R.n || L.m != R.m) return L;
    Matrix M;
    for(int i = 0;i < L.n; ++i) {
        for(int j = 0;j < L.m; ++j){
            M.mp[i][j] = L.mp[i][j] + R.mp[i][j];
        }
    }
    return M;
}


Matrix reduce(Matrix L,Matrix R) {//减法
    if(L.n != R.n || L.m != R.m) return L;
    Matrix M;
    for(int i = 0;i < L.n; ++i) {
        for(int j = 0;j < L.m; ++j){
            M.mp[i][j] = L.mp[i][j] - R.mp[i][j];
        }
    }
    return M;
}

Matrix mult(Matrix L,Matrix R) {//乘法
    if(L.n != R.m || L.m != R.n) return L;
    Matrix M;
    for(int i = 0;i < L.n; ++i) {
        for(int j = 0;j < R.m; ++j){
            for(int k = 0;k < L.m; ++k) {
                M.mp[i][j] += L.mp[i][k] * R.mp[k][j];
            }
        }
    }
    return M;
}

int main()
{
    Matrix a,b;
    a.init(2,2);
    b.init(2,2);

    for(int i = 0;i < 2; ++i) {
        for(int j = 0;j < 2; ++j) {
            a.mp[i][j] = i * 2 + j;
            b.mp[i][j] = i * 2 + j;
        }
    }
    Matrix c = mult(a,b);
    for(int i = 0;i < 2; ++i) {
        for(int j = 0;j < 2; ++j) {
            printf("%d ",c.mp[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

六、快速幂&龟速乘¶

6.1快速幂¶

6.1.1 问题引出¶

给出三个数a、b、c,求\(a^b \ mod \ c\)

运用前面学到的同余，我们可以直接对a进行乘b次然后取模c，但是当b很大的时候怎么办呢？这时候就要用到了今天的内容，快速幂，快速幂作为一个基础的知识，在很多的地方都会用到它，例如求高幂运算，求逆元、矩阵快速幂等

6.1.2 原理¶

快速幂的原理其实用到了位运算的知识，我们的关注点应该是这个幂b，之前的方法是直接循环乘b次，但是当b很大例如1e9的时候就不满足时间复杂度，我们可以将这个b先转化为二进制，我举个栗子：

例如b = 11，那么它的二进制就为1011B，也就是说我们要求的这个\(a^b \ = \ a^1 \times a^2 \times a ^ 8\) 不难看出我们将这个b分解成了若干个2的幂的积，我们通过位运算只需要通过不断的左移维护一个2的幂的值即可，当该位为1那么就乘上它，这就是快速幂的原理，时间复杂度为\(log_b\)

6.1.3 代码¶

//快速幂 
ll ksm(ll x, ll n, ll mod) {
    ll res = 1;
    while(n > 0) {
        if(n & 1)    
            res = (res * x)% mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return res;
}

6.2广义幂¶

6.2.1问题引出¶

已知数列 \(a_1,a_2……a_n\)和\(C\)

计算 \((a_1 \times a_2 \times ……\times a_n) \%C\)的结果

6.2.2原理¶

设：○为一种运算且与集合V构成群，a∈V，e为○运算的幺元。

即e满足对于任意的a,有 \(e○a\ = \ a○e\ =\ a\)

我们可以记

\(a^○=e\)

\(a_n\ =\ a_{n-1}\ ○\ a\)

则有以下性质

\(a_n\ +\ m\ =\ a_n\ ○\ a_m\)

则此时计算a关于○运算的n次幂的快速幂可以这样写

res=e;temp=a;
while(n)
{
    if(n&1)
        res=res○temp;
    temp=temp○temp;
    n>>=1;

}
return res;

然后就像\(a^b=a\times a\times a\times a\times a…\) 是关于乘法的幂运算，又因为\(1\times a\ =\ a \times 1 \ =\ a\),所以乘法幺元e就是1，带入上面的程序就可以得到最常见的乘法快速幂,下面的龟速乘同理

6.3 龟速乘法¶

6.3.1问题引出¶

如果我们想要计算两个大整数A、B(long long范围内)的乘法并取模C怎么办呢？手动写高精度吗？显然不需要，这里就能用到我们现在要学的龟速乘法

6.3.2原理¶

和上面的快速乘同理，不难看出此处的此处的乘法幺元就是0，如果还是不懂请看上面的广义幂的原理

6.3.3 代码¶

ll gsc(ll x, ll n, ll mod) {
    ll res = 0;
    x%= mod;
    n%= mod;
    while(n) {
        if(n & 1) 
            res = (res + x) % mod;
        x = (x%mod + x%mod) % mod;
        n >>= 1;
    }
    return res%mod;
}

七、矩阵快速幂¶

7.1问题引出¶

求一个\(N\times N\)矩阵的K次幂

我们之前学过矩阵的加减乘，知道乘法的复杂度为\(O(N^3)\)的，如果朴素的做法就是\(O(N^3 \times k)\)的，当k很小的时候我们这样计算倒没问题，但是当k很大的时候呢，这时候就需要到这一小节的内容，矩阵快速幂

7.2原理¶

原理参见上面的广义幂，实质和快速幂，龟速乘等没有太大区别只不过幺元不同,此处的幺元变成了单位矩阵（主对角线全为1，其余为0），运算方式变成了矩阵乘法

7.3 代码¶

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

#define N 200

struct Matrix{
    ll mp[N][N];
};
Matrix loc;

ll n,k;

Matrix operator*(const Matrix &x, const Matrix &y) {
    Matrix a;
    memset(&a,0,sizeof(a));
    for(int i = 1;i <= n; ++i) 
        for(int j = 1;j <= n; ++j)
            for(int k = 1;k <= n; ++k)
                a.mp[i][j] = ((a.mp[i][j] + x.mp[i][k] * y.mp[k][j]) % mod) %mod;
    return a;
}

void ksm(ll k) {
    Matrix ans;
    for(int i = 1;i <= n; ++i)
        for(int j = 1;j <= n; ++j)
            ans.mp[i][j] = i==j;
    while(k) {
        if(k & 1) ans = ans * loc;
        loc = loc * loc;
        k>>=1;
    }
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= n; ++j) {
            printf("%lld ",ans.mp[i][j]);
        }
        putchar('\n');
    }
}

int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i = 1;i <= n; ++i)
        for(int j = 1;j <= n; ++j)
            scanf("%lld",&loc.mp[i][j]);
    ksm(k);
    return 0;
}

7.5矩阵快速幂求解斐波那契问题¶

7.5.1 问题引出¶

众所周知斐波那契问题\(F_n = F_{n-1} + F_{n-2}\)，我们可以通过递推式求出取模情况下的第N项的值，但是如果N很大呢（比如1e18），这时候怎么办呢？

7.5.2 思路¶

很显然我们能想到用一个矩阵乘法来表达这个递推过程

\[ \begin{bmatrix} F_{n-1} & F_{n} \end{bmatrix} =\begin{bmatrix} F_{n-2} & F_{n-1} \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \]

然后我们此时假设P=\(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) 就能得到斐波那契的矩阵递推式：

\[ \begin{bmatrix} F_n & F_{n-1} \\ \end{bmatrix} =\begin{bmatrix} F_0 & F_1 \\ \end{bmatrix} \times P^n \]

我们就能在\(log_n\)的时间复杂度求出\(F_n\)了

7.5.3 斐波那契数列性质¶

卡西尼性质（Cassini's identity）：\(F_{n-1}\times F_{n+1} - F_n^2\ = (-1)^n\)
附加性质：\(F_n+k \ = \ F_k F_{n+1} + F_{k-1}F_n\)
GCD 性质：\((F_m,F_n) \ = \ F_{(m,n)}\)

八、费马小定理求逆元¶

8.1 费马小定理¶

若P为质数，\(GCD(a,p) = 1\)，则\(a^{p-1} ≡ 1 \ (mod \ p)\)

换句话说：对于任意整数a，有\(a^p = a \ (mod \ p)\)

8.2 逆元¶

8.2.1 简介¶

如果一个线性同余方程\(ax ≡ 1 \ (mod \ p)\)，则x被称作为\(a \ mod \ p\)的逆元，记作\(a^{-1}\)

8.2.2 如何求¶

有两种方法 扩展欧几里得法 和 快速幂法

我们这里只介绍快速幂的方法：

用到了上面的前置知识：费马小定理

由上面可得：a的乘法逆元为\(a^{p-2}\)

九、训练题单¶

http://acm.mangata.ltd/training/61d167fb9583df9f1d5e39f2

最后更新: 2022-09-18 09:51:05