2022_HAUE_计算机学院暑期培训——扩展欧几里得算法

2022-09-16 19:23:46 浏览数 (2)

​

1. 预习内容

1.1 阅读资料

  • 欧几里得算法
  • 裴蜀定理
  • 同余定理
  • 线性同余方程

1.2 练习题目

例题1 两个数的最大公约数

原题链接

描述

输入2个正整数a，b，求a与b的最大公约数。

输入

2个正整数a，b，中间用空格隔开。(1<=a,b <= 104)

输出

输出a与b的最大公约数。

样例输入

代码语言：javascript复制
6 15

样例输出

代码语言：javascript复制
3

代码 1

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

int main(){

    int a, b;

    cin >> a >> b;

    int flag = 1;

    for(int i = 2; i <= min(a,b); i  ){
        if(a % i == 0 && b % i == 0) flag = max(flag,i);
    }

    cout << flag << "n";

    return 0;

}

代码 2

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

int gcd(int a, int b){
    return b ? gcd(b,a%b) : a;
}

int main(){

    int a, b;

    cin >> a >> b;

    cout << gcd(a,b) << "n";

    return 0;

}

2. 课程内容

2.1 数论简介

数学题在算法竞赛中经常出现，在竞赛中经常把数学模型和其他算法结合起来，出综合性的题目。

分类：

  • 整除性问题:整除、最大公约数、最大公倍数;欧几里得算法、扩展欧几里得算法。
  • 公式计算：高精度计算、概率和数学期望
  • 素数问题:素数判定、筛法、区间素数统计。
  • 同余问题:模运算、同余方程、快速幂、中国剩余定理、逆元、整数分解、同余定理、不定方程。
  • 积性函数:欧拉函数、伪随机数、莫比乌斯反演。
  • 多项式与生成函数：快速傅里叶变换、普通生成函数、指数生成函数。
  • 递推关系:Fibonacci数列、Stirling数、Catalan数。
  • 群论:Polya定理。
  • 线性规划:单纯形法。
  • 线性代数：矩阵、高斯消元。
  • 博弈论：公平组合游戏、非公平组合游戏。
  • 排列组合:容斥原理、抽屉原理、康托展开、排列生成、组合生成

特点

  • 涉及大量数学定理、数学模型和公式计算，综合程度高
  • 需要将题目抽象出其数学模型，或根据条件推理出规律进行求解

2.2 欧几里得算法

1. 简介与证明

概念

  • 最大公约数指两个或多个整数共有约（因）数中最大的数
  • 最小公倍数指两个或多个整数的公倍数里最小的数
  • 欧几里得算法：又称辗转相除法，用于计算两个非负整数 a 和 b 的最大公约数

思想

  • 辗转相除法求最大公约数 求100和18的最大公约数？

`$

begin{aligned}

&1.令a_0=100，b_0=18\

&lfloor frac{a_0}{b_0} rfloor = 5，a_0-lfloor frac{a_0}{b_0} rfloortimes b_0 = 10\

&2.令a_1=b_0=18，b_1=a_0~mod~b_0=10\

&lfloor frac{a_1}{b_1} rfloor = 1，a_1-lfloor frac{a_1}{b_1} rfloortimes b_1 = 8\

&3.令a_2=b_1=10，b_2=a_1~mod~b_1=8\

&lfloor frac{a_2}{b_2} rfloor = 1，a_2-lfloor frac{a_2}{b_2} rfloortimes b_2 = 2\

&4.令a_3=b_2=8，b_3=a_2~mod~b_2=2\

&lfloor frac{a_3}{b_3} rfloor = 0，a_3-lfloor frac{a_3}{b_3} rfloortimes b_3 = 4\

&即最大公约数为b_3=2

end{aligned}

$`

求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

100 / 18 = 5 (余 10) 100%8=10

18 / 10= 1(余8) 18=8

10 / 8 = 1(余2) 10%8=2

8 / 2 = 4 (余0) 8%2=0

至此，最大公约数为2

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。

  • 求N 和M 的最小公倍数lcm(N,M) ，则先求N 和M 的最大公约数gcd(N,M) ，然后frac{Ntimes M}{gcd(N,M)} 则为最小公倍数。
2. 算法模板
代码语言：javascript复制
//最大公约数
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

//最小公倍数
int lcm(int a,int b){
    return a / gcd(a,b) * b;
}
3. 最大公约数

原题链接

描述

输入两个正整数a、b，求a、b的最大公约数。要求采用递归函数实现。

输入

输入两个正整数a、b。

输出

输出a、b的最大公约数。

代码语言：javascript复制
20 15

样例输出

样例输出

代码语言：javascript复制
5

代码

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

int gcd(int a, int b){
    return b ? gcd(b,a % b) : a;
}

int main(){

    int a, b;

    cin >> a >> b;

    cout << gcd(a,b) << "n";

    return 0;

}
4. 多个数的最小公倍数

原题链接

题目描述

输入n个数，请计算它们的最小公倍数。如5、7、15的最小公倍数是105。

输入

首先输入一个正整数T,表示测试数据的组数，然后是T组的测试数据。

每组测试先输入一个整数n（2<=n<=20),再输入n个正整数（n属于1,100000),这里保证最终的结果在int型范围内。

输出

对于每组测试，输出n个整数的最小公倍数。

样例输入

代码语言：javascript复制
2
3 5 7 15
5 1 2 4 3 5

样例输出

代码语言：javascript复制
105
60

分析

  • 求多个数的最小公倍数，可以两两相求

代码

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

int gcd(int a,int b){
    return b ? gcd(b,a % b) : a;
}

int lcm(int a,int b){
    return a / gcd(a,b) * b;
}

void solve(){

    int n;

    cin >> n;

    int t;

    cin >> t;

    for(int i = 2; i <= n ; i  ){
        int x;
        cin >> x;

        t = lcm(t,x);

        if(i == n) cout << t << 'n';

    }

}

int main(){

    int _;

    cin >> _;

    while(_--){
        solve();
    }

    return 0;

}

2.3 扩展欧几里得算法

1. 简介与证明

作用

  • 求形如ax by=gcd(a,b) 的方程的解x,y

思想

  • 欧几里得算法：gcd(a,b)=gcd(b,a%b) ，特别的gcd(a,0)=a
  • 裴蜀定理：对于任意正整数a,b ，一定存在非零的x,y ，使得ax by=gcd(a,b)

`$

begin{cases}

b=0时:begin{cases}

gcd(a,b)=aax by=gcd(a,b)

end{cases}Rightarrowbegin{cases}x=1y=0end{cases}

bneq0时：

begin{cases}

begin{aligned}

①&设~ax by=gcd(a,b)=d\

&because 由欧几里得算法可知：gcd(a,b)=gcd(b,a%b)=d\

&therefore 由裴蜀定理得：b{x}' (a%b){y}'=d\

又&because ax by=d\

&therefore联立

begin{cases}

ax by=db{x}' (a%b){y}'=da%b=a-lfloorfrac{a}{b}rfloor b

end{cases}Rightarrowbegin{cases}x={y}'y={x}'-lfloorfrac{a}{b}rfloor{y}'end{cases}\

②&设{a}'=b,{b}'=a%b\

&therefore gcd(b,a%b)=gcd({a}',{b}')=d\

&because gcd({a}',{b}')=gcd({b}',{a}'%{b}')=d\

&therefore {b}'{x}'' {a}'%{b}'{y}''=d\

又&because b{x}' (a%b){y}'=d\

&therefore联立begin{cases}

b{x}' (a%b){y}'=d{b}'{x}'' {a}'%{b}'{y}''=d{a}'%{b}'={a}'-lfloorfrac{{a}'}{{b}'}rfloor{b}'

end{cases}Rightarrowbegin{cases}{x}'={y}''{y}'={x}''-lfloorfrac{{a}'}{{b}'}rfloor{y}''

end{cases}\

③&设{a}''={b}',{b}''={a}'%{b}'\

&dots

&dots

&直到b=0时，联立解得begin{cases}{x}^i=1{y}^i=0end{cases}\

&然后逐步返回每一次联立所得的结果begin{cases}{x}^{i-1}={y}^{i}{y}^{i-1}={x}^{i}-lfloorfrac{{a}^{i}}{{b}^i}rfloor{y}^{i}

&最后返回得到x和y的值

end{cases}

end{aligned}

end{cases}

end{cases}

$`

注意

  • 当方程符合ax by=gcd(a,b) 的形式时，才可以用扩展欧几里得算法求解(x_0,y_0)
  • 推论：可以进一步求解任意方程ax by=n ，得到一个整数解

`$

begin{aligned}

begin{cases}

&(1)~~判断方程ax by=n是否有整数解，有解的条件为：gcd(a,b)可以整除n\

&(2)~~用扩展欧几里得算法求ax by=gcd(a,b)得到一个解(x_0,y_0)\

&(3)~~在ax_0 by_0=gcd(a,b)两边同时乘frac{n}{gcd(a,b)}Rightarrowfrac{ax_0n}{gcd(a,b)} frac{by_0n}{gcd(a,b)}=n\

&(4)~~对照ax by=n可知该方程的一个解为({x}',{y}')，其中begin{cases}{x}'=frac{x_0n}{gcd(a,b)}\{y}'=frac{y_0n}{gcd(a,b)} end{cases}

end{cases}

end{aligned}

$`

2. 算法模板
代码语言：javascript复制
void exgcd(int a, int b, int &x, int &y){

    if(!b){  //若b=0时
        x = 1,y = 0;
        return ;
    }
    else{  //b!=0时
        exgcd(b, a % b, x, y);  //递归到下一层
        int t = x;  //返回时执行
        x = y;
        y = t - a / b * y;
    }

}
3. 解ax by=gcd(a,b)方程

原题链接

描述

给定n 对正整数 a_i,b_i ，对于每对数，求出一组 x_i,y_i ，使其满足 a_i×x_i b_i×y_i=gcd(a_i,b_i) 。

输入格式 第一行包含整数 n 。

接下来 n 行，每行包含两个整数 a_i,b_i 。

输出格式 输出共 n 行，对于每组a_i,b_i ，求出一组满足条件的 x_i,y_i ，每组结果占一行。

本题答案不唯一，输出任意满足条件的 x_i,y_i 均可。

数据范围 1≤n≤105, 1≤a_i,b_i≤2×10^9 输入样例：

代码语言：javascript复制
2
4 6
8 18

输出样例：

代码语言：javascript复制
-1 1
-2 1

代码

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

void exgcd(int a,int b,int &x,int &y){

    if(!b){x=1,y=0;
        return ;}
    else{

        exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
    }

}

int main(){

    int n;

    cin>>n;

    while(n--){

        int a,b,x,y;

        cin>>a>>b;

        exgcd(a,b,x,y);

        cout<<x<<" "<<y<<endl;

    }

    return 0;

}
4. 解一元线性同余方程

概念

  • axequiv b(mod~m) ，即frac{ax}{m} 与frac{b}{m} 的余数相同，且a,b,m 为整数，求x 的值
  • 该方程即为一元线性同余方程

思想

  • 对axequiv b(mod~m) 做等价变形：ax my=b

​

​

`$

$`

  • 由扩展欧几里得算法的推论可知：当且仅当 gcd(a,m) 可以整除b 时，ax my=b 存在整数解

`$

由扩展欧几里得算法可知：

begin{cases}

当gcd(a,m)=b时：begin{cases}x=x_0y=y_0end{cases}\

当gcd(a,m)为b的整数倍时：begin{cases}{x}'=frac{x_0b}{gcd(a,m)}{y}'=frac{y_0b}{gcd(a,m)}end{cases}

end{cases}

$`

例题 878. 线性同余方程

原题链接

描述

给定 n 组数据 a_i,b_i,m_i ，对于每组数求出一个 x_i ，使其满足 a_i×x_i≡b_i(mod~m_i) ，如果无解则输出 impossible。

输入格式 第一行包含整数 n 。

接下来 n 行，每行包含一组数据 a_i,b_i,m_i 。

输出格式 输出共 n 行，每组数据输出一个整数表示一个满足条件的 x_i ，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

数据范围 1≤n≤105 , 1≤a_i,b_i,m_i≤2×10^9

代码语言：javascript复制
2
2 3 6
4 3 5

输出样例：

输出样例：

代码语言：javascript复制
impossible
-3

代码

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

typedef long long LL;

LL gcd(LL a,LL b){
    return b ? gcd(b,a % b) : a;
}

void exgcd(LL a,LL b,LL &x,LL &y){

    if(!b){  //若b=0时
        x=1,y=0;
        return ;
    }
    else{
        exgcd(b,a%b,x,y);
        LL t=x;
        x=y;
        y=t-a/b*y;
    }

}

int main(){

    int n;

    cin>>n;

    while(n--){

        LL a,b,m,x,y;

        cin>>a>>b>>m;

        LL d=gcd(a,m);

        exgcd(a,m,x,y);

        if(b%d) cout<<"impossible"<<endl;
        else cout<<b/d*x%m<<endl;

    }

    return 0;

}

3. 推荐阅读

  • OI WIKI
  • 基础数学初识
海外加速 编程算法

0 人点赞