跳转至

img

基础数论

0、前言

同余、GCD、LCM、拓展GCD

视频链接:

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

素数相关

视频链接: https://www.bilibili.com/video/BV1Cu411U7Ls/

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

视频链接:

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=restemp;
    temp=temptemp;
    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

评论

回到页面顶部