2022_HAUE_计算机学院暑期培训——扩展欧几里得算法
本文最后更新于 906 天前,其中的信息可能已经有所发展或是发生改变。

1. 预习内容


1.1 阅读资料


1.2 练习题目


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

原题链接

描述

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

输入

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

输出

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

样例输入

6 15

样例输出

3

代码 1

#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

#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. 简介与证明


概念

  • 最大公约数指两个或多个整数共有约(因)数中最大的数
  • 最小公倍数指两个或多个整数的公倍数里最小的数
  • 欧几里得算法:又称辗转相除法,用于计算两个非负整数 aabb最大公约数

思想

  • 辗转相除法求最大公约数

    求100和18的最大公约数?

  • 1.a0=100b0=18a0b0=5a0a0b0×b0=102.a1=b0=18b1=a0 mod b0=10a1b1=1a1a1b1×b1=83.a2=b1=10b2=a1 mod b1=8a2b2=1a2a2b2×b2=24.a3=b2=8b3=a2 mod b2=2a3b3=0a3a3b3×b3=4即最大公约数为b3=2 \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} \rfloor\times 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} \rfloor\times 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} \rfloor\times 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} \rfloor\times b_3 = 4\\\\ &即最大公约数为b_3=2 \end{aligned}

    求 100 和18 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
    100 / 18 = 5 (余 10) 100%8=10
    18 / 10= 1(余8) 18%10=8
    10 / 8 = 1(余2) 10%8=2
    8 / 2 = 4 (余0) 8%2=0
    至此,最大公约数为2
    以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 100 和 18 的最大公约数2。

  • NNMM的最小公倍数lcm(N,M)lcm(N,M),则先求NNMM的最大公约数gcd(N,M)gcd(N,M),然后N×Mgcd(N,M)\frac{N\times M}{gcd(N,M)}则为最小公倍数。


2. 算法模板


//最大公约数
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的最大公约数。

20 15

样例输出

样例输出

5

代码

#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个整数的最小公倍数。

样例输入

2
3 5 7 15
5 1 2 4 3 5

样例输出

105
60

分析

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

代码

#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)ax+by=gcd(a,b)的方程的解x,yx,y

思想

  • 欧几里得算法:gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b),特别的gcd(a,0)=agcd(a,0)=a

  • 裴蜀定理:对于任意正整数a,ba,b,一定存在非零的x,yx,y,使得ax+by=gcd(a,b)ax+by=gcd(a,b)

  • {b=0:{gcd(a,b)=aax+by=gcd(a,b){x=1y=0b0时:{设 ax+by=gcd(a,b)=d由欧几里得算法可知:gcd(a,b)=gcd(b,a%b)=d由裴蜀定理得:bx+(a%b)y=dax+by=d联立{ax+by=dbx+(a%b)y=da%b=aabb{x=yy=xabya=b,b=a%bgcd(b,a%b)=gcd(a,b)=dgcd(a,b)=gcd(b,a%b)=dbx+a%by=dbx+(a%b)y=d联立{bx+(a%b)y=dbx+a%by=da%b=aabb{x=yy=xabya=b,b=a%b直到b=0时,联立解得{xi=1yi=0然后逐步返回每一次联立所得的结果{xi1=yiyi1=xiaibiyi最后返回得到xy的值 \begin{cases} b=0时:\begin{cases} gcd(a,b)=a\\ax+by=gcd(a,b)\\ \end{cases}\Rightarrow\begin{cases}x=1\\y=0\end{cases} \\ \\ \\ \\ \\ b\neq0时: \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=d\\b{x}'+(a\%b){y}'=d\\a\%b=a-\lfloor\frac{a}{b}\rfloor b \end{cases}\Rightarrow\begin{cases}x={y}'\\y={x}'-\lfloor\frac{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}'-\lfloor\frac{{a}'}{{b}'}\rfloor{b}' \end{cases}\Rightarrow\begin{cases}{x}'={y}''\\{y}'={x}''-\lfloor\frac{{a}'}{{b}'}\rfloor{y}'' \end{cases}\\\\ ③&设{a}''={b}',{b}''={a}'\%{b}'\\\\ &\dots\\ &\dots\\ &直到b=0时,联立解得\begin{cases}{x}^i=1\\{y}^i=0\end{cases}\\\\ &然后逐步返回每一次联立所得的结果\begin{cases}{x}^{i-1}={y}^{i}\\{y}^{i-1}={x}^{i}-\lfloor\frac{{a}^{i}}{{b}^i}\rfloor{y}^{i} &最后返回得到x和y的值 \end{cases}\\ \end{aligned} \end{cases} \end{cases}

注意

  • 当方程符合ax+by=gcd(a,b)ax+by=gcd(a,b)的形式时,才可以用扩展欧几里得算法求解(x0,y0)(x_0,y_0)

  • 推论:可以进一步求解任意方程ax+by=nax+by=n,得到一个整数解

  • {(1)  判断方程ax+by=n是否有整数解,有解的条件为:gcd(a,b)可以整除n(2)  用扩展欧几里得算法求ax+by=gcd(a,b)得到一个解(x0,y0)(3)  在ax0+by0=gcd(a,b)两边同时乘ngcd(a,b)ax0ngcd(a,b)+by0ngcd(a,b)=n(4)  对照ax+by=n可知该方程的一个解为(x,y),其中{x=x0ngcd(a,b)y=y0ngcd(a,b) \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)}\Rightarrow\frac{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. 算法模板


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)方程

原题链接

描述

给定nn对正整数 ai,bia_i,b_i,对于每对数,求出一组 xi,yix_i,y_i,使其满足 ai×xi+bi×yi=gcd(ai,bi)a_i×x_i+b_i×y_i=gcd(a_i,b_i)

输入格式
第一行包含整数 nn

接下来 nn 行,每行包含两个整数 ai,bia_i,b_i

输出格式
输出共 nn 行,对于每组ai,bia_i,b_i,求出一组满足条件的 xi,yix_i,y_i,每组结果占一行。

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

数据范围
1n105,1≤n≤105,
1ai,bi2×1091≤a_i,b_i≤2×10^9
输入样例:

2
4 6
8 18

输出样例:

-1 1
-2 1

代码

#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. 解一元线性同余方程


概念

  • axb(mod m)ax\equiv b(mod~m),即axm\frac{ax}{m}bm\frac{b}{m}的余数相同,且a,b,ma,b,m为整数,求xx的值
  • 该方程即为一元线性同余方程

思想

  • axb(mod m)ax\equiv b(mod~m)做等价变形:ax+my=bax+my=b

  • axb(mod m)ax%m=k(b%m),(kZ)axaxmm=k(bbmm)axkb=(axmkbm)maxm,bm,kZ(axmkbm)Z(axmkbm)=y,(yZ)axkb=myaxmy=by可以为负数axb(mod m)ax+my=b \begin{aligned} &\because &ax&\equiv b(mod~m)\\\\ &\therefore &ax\%m&=k(b\%m),(k\in \Z)\\\\ &\therefore &ax-\lfloor\frac{ax}{m}\rfloor m&=k(b-\lfloor\frac{b}{m}\rfloor m)\\\\ &\therefore &ax-kb&=(\lfloor\frac{ax}{m}\rfloor-k\lfloor\frac{b}{m}\rfloor)m\\\\ &\because &\lfloor\frac{ax}{m}\rfloor,&\lfloor\frac{b}{m}\rfloor,k\in \Z\\\\ &\therefore &(\lfloor\frac{ax}{m}\rfloor&-k\lfloor\frac{b}{m}\rfloor)\in \Z\\\\ &&设(\lfloor\frac{ax}{m}\rfloor&-k\lfloor\frac{b}{m}\rfloor)=y,(y\in \Z)\\\\ &\therefore &ax-kb&=my\Rightarrow ax-my=b\\\\ 又&\because &y&可以为负数\\\\ &\therefore &ax\equiv b(mod~&m)\leftrightarrow ax+my=b \end{aligned}
  • 由扩展欧几里得算法的推论可知:当且仅当gcd(a,m) gcd(a,m)可以整除bb时,ax+my=bax+my=b存在整数解

  • 由扩展欧几里得算法可知:{gcd(a,m)=b时:{x=x0y=y0gcd(a,m)b的整数倍时:{x=x0bgcd(a,m)y=y0bgcd(a,m) 由扩展欧几里得算法可知: \begin{cases} 当gcd(a,m)=b时:\begin{cases}x=x_0\\y=y_0\end{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. 线性同余方程

原题链接

描述

给定 nn 组数据 ai,bi,mia_i,b_i,m_i,对于每组数求出一个 xix_i,使其满足 ai×xibi(mod mi)a_i×x_i≡b_i(mod~m_i),如果无解则输出 impossible

输入格式
第一行包含整数 nn

接下来 nn 行,每行包含一组数据 ai,bi,mia_i,b_i,m_i

输出格式
输出共 nn 行,每组数据输出一个整数表示一个满足条件的 xix_i,如果无解则输出 impossible

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

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

数据范围
1n1051≤n≤105,
1ai,bi,mi2×1091≤a_i,b_i,m_i≤2×10^9

2
2 3 6
4 3 5

输出样例:

输出样例:

impossible
-3

代码

#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. 推荐阅读


暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇