蓝桥集训之数论基础

视频讲解链接 同余、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 ) m o d      n = ( ( a m o d      n ) + ( b m o d      n ) ) m o d      n (a+b) \mod \ n = ((a \mod \ n) + (b \mod \ n) )\mod \ n (a+b)mod n=((amod n)+(bmod n))mod n
• ( a − b ) m o d      n = ( ( a m o d      n ) − ( b m o d      n ) ) m o d      n (a-b) \mod \ n = ((a \mod \ n) - (b \mod \ n) )\mod \ n (a−b)mod n=((amod n)−(bmod n))mod n
• ( a × b ) m o d      n = ( ( a m o d      n ) × ( b m o d      n ) ) m o d      n (a \times b) \mod \ n = ((a \mod \ n) \times (b \mod \ n) )\mod \ n (a×b)mod n=((amod n)×(bmod 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)
            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也就出来了， L C M   =   a × b G C D ( a , b ) LCM\ = \ \frac{a \times b}{GCD(a, b)} LCM = GCD(a,b)a×b​

2.3 拓展欧几里得 2.3.1 前置知识

辗转相除法、贝祖定理

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

贝祖定理证明：

设 s = g c d ( a , b ) s=gcd(a,b) s=gcd(a,b)，显然 s ∣ a s|a s∣a，并且 s ∣ b s|b s∣b

又因为 x ， y ∈ Z x，y∈Z x，y∈Z

所以 s ∣ a x s|ax s∣ax, s ∣ b y s|by s∣by

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

又因为 x x x和 y y y是正整数

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

因此，证得该定理成立

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

2.3.2 问题引出

求得任意一组解： a x + b y = 1 ax+by=1 ax+by=1

2.3.3 思路

很显然，我们能知道如果 g c d ( a , b ) ! = 1 gcd(a,b)!=1 gcd(a,b)!=1的话是无解的，所以我们只看 g c d ( a , b ) = 1 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 原理证明

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

①设 a x + b y = t ax+by=t ax+by=t

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

② 当b不等于0时

设 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b) —Ⅰ

我们可以推出下一层的状态： b x ′ + ( a % b ) y ′ = g c d ( b , a % b ) bx'+(a\%b)y'=gcd(b,a\%b) bx′+(a%b)y′=gcd(b,a%b) — Ⅱ

又因为 g c d ( b , a % b ) = g c d ( a , b ) gcd(b,a\%b)=gcd(a,b) gcd(b,a%b)=gcd(a,b) — Ⅲ

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

又因为 a % b = a − ⌊ a b ⌋ × b a\%b = a - \left \lfloor \frac{a}{b} \right \rfloor \times b a%b=a−⌊ba​⌋×b — Ⅵ

所以由Ⅴ、Ⅵ可得： a x + b y = a ∗ y ′ + b × ( x ′ − ⌊ a b ⌋ × y ′ ) ax + by = a*y' + b\times (x'- \left \lfloor \frac{a}{b} \right \rfloor \times y') ax+by=a∗y′+b×(x′−⌊ba​⌋×y′)

所以可以得到： x = y ′ , y = x ′ − ⌊ a b ⌋ × y ′ x = y',y = x'- \left \lfloor \frac{a}{b} \right \rfloor \times y' x=y′,y=x′−⌊ba​⌋×y′

三、唯一分解定理 3.1 理论

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

3.2习题

http://120.78.128.11/Challenge.jsp#B213

四、素数三大筛 4.1 朴素素数筛 4.1.1 原理

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

4.1.2 代码

bool is_prime(int x) {
    if(x == 0 || x == 1)
    return false;
    for(int i = 2; i*i \ prime[j] \times k 
         
        
      prime[j+1]×k > prime[j]×k
 
 
∴  
       
        
         
         
           p 
          
         
           r 
          
         
           i 
          
         
           m 
          
         
           e 
          
         
           [ 
          
         
           j 
          
         
           + 
          
         
           1 
          
         
           ] 
          
         
           × 
          
         
           ( 
          
         
           k 
          
         
           × 
          
         
           p 
          
         
           r 
          
         
           i 
          
         
           m 
          
         
           e 
          
         
           [ 
          
         
           j 
          
         
           ] 
          
         
           ) 
          
         
           = 
          
         
           x 
          
         
           = 
          
         
           i 
          
         
           × 
          
         
           p 
          
         
           r 
          
         
           i 
          
         
           m 
          
         
           e 
          
         
           [ 
          
         
           j 
          
         
           + 
          
         
           1 
          
         
           ] 
          
         
        
          prime[j+1] \times (k \times prime[j]) = x = i \times prime[j+1] 
         
        
      prime[j+1]×(k×prime[j])=x=i×prime[j+1]
 
 
所以可得， 
       
        
         
         
           i 
          
         
           × 
          
         
           p 
          
         
           r 
          
         
           i 
          
         
           m 
          
         
           e 
          
         
           [ 
          
         
           j 
          
         
           + 
          
         
           1 
          
         
           ] 
          
         
        
          i \times prime[j+1] 
         
        
      i×prime[j+1]必然会在以后被 
       
        
         
         
           p 
          
         
           r 
          
         
           i 
          
         
           m 
          
         
           e 
          
         
           [ 
          
         
           j 
          
         
           ] 
          
         
        
          prime[j] 
         
        
      prime[j]的 
       
        
         
         
           k 
          
         
           × 
          
         
           p 
          
         
           r 
          
         
           i 
          
         
           m 
          
         
           e 
          
         
           [ 
          
         
           j 
          
         
           + 
          
         
           1 
          
         
           ] 
          
         
        
          k \times prime[j + 1] 
         
        
      k×prime[j+1]倍数删掉
 
 
后面的数字同理
 
 
4.3.2 代码 
/*
    作者:Mangata
    欧拉筛模板     
*/
//时间复杂度为  O(n) 
#include
#include
#include
#include

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