最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球信息:数学知识1.4

来源：博客园

一、简述

记录有关拓展欧几里得算法。


【资料图】

二、拓展欧几里得算法

裴蜀定理：若 \(a,b\) 是整数，且 \(a\) 和 \(b\) 的最大公约数 \(gcd(a, b)=d\)，那么任意的整数 \(x,y\)，\(ax+by\) 一定是 \(d\) 的整数倍。特别地，一定存在整数 \(x,y\) 使得 \(ax+by=d\)。

对于任意的 \(a,b\in Z\)，\(gcd(a,b)=d\)，则关于 \(x,y\) 的线性丢番图方程(裴蜀等式)：\(ax+by=m\)，有整数解 \((x,y)\) 当且仅当 \(m\) 是 \(d\) 的倍数。裴蜀等式有解时必然存在无穷多解(例如：\(ax+by=m\)，则 \((x-k\frac{b}{m},y+k\frac{a}{m})\)，\(k\) 为整数)。

裴蜀定理的一个重要推论：\(a\) 和 \(b\) 互质的充要条件是存在整数 \((x,y)\) 使得 \(ax+by=1\)。

拓展欧几里得算法：对正整数 \(a,b\)，有整数解 \((x,y)\)，使其满足 \(ax+by=gcd(a,b)\)。求解思路如下：① 若 \(b=0\)，则 \(gcd(a,b)=a\)，则可取 \(x=1,y=0\) 使得 \(ax+by=gcd(a,b)=a\)。② 若 \(b\neq0\)，则 \(ax+by=gcd(a,b)=gcd(b,a{\%}b)=d\)。而 \(bx"+(a\%b)y"=gcd(b,a\%b)=d\)，而 \(a\%b=a-\lfloor {\frac{a}{b}} \rfloor ·b\)，那么就可以得到 \(bx"+(a-\lfloor {\frac{a}{b}} \rfloor ·b)y"=d=ax+by\)，展开得到 \(ay"+b(x"-\lfloor {\frac{a}{b}} \rfloor·y")=ax+by\)，等价得到 \(ax"+b(y"-\lfloor {\frac{a}{b}} \rfloor·x")=ax+by\)，\(x=x",y=y"-\lfloor {\frac{a}{b}} \rfloor·x"\)。

模板题AcWing 877. 扩展欧几里得算法

题目描述

给定 \(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≤10^5,1≤a_i,b_i≤2×10^9\)

输入样例
24 68 18
输出样例
-1 1-2 1
C++代码
#include using namespace std;int n;int exgcd(int a, int b, int &x, int &y){    if(!b)    {        x = 1, y = 0;        return a;    }    int d = exgcd(b, a % b, y, x);    y -= a / b * x;    return d;}int main(){    scanf("%d", &n);    while(n --)    {        int a, b, x, y;        scanf("%d%d", &a, &b);        exgcd(a, b, x, y);        printf("%d %d\n", x, y);    }    return 0;}

三、线性同余方程

\(ax\equiv b(mod\,m)\) 的方程。此方程有解当且仅当 \(b\) 能够被 \(a\) 与 \(m\) 的最大公约数整除，记作 \(gcd(a,m) | b\)。这时，如果 \(x_0\) 是方程的一个解，那么所有的解可以表示为：{\(x_0+k\frac{n}{d}|(k∈z)\)}，其中 \(d\) 是 \(a\) 与 \(m\) 的最大公约数。在模 \(m\) 的完全剩余系 {\(0,1,…,n-1\)} 中，恰有 \(d\) 个解。由 \(ax\equiv b(mod\,m)\)，则存在整数 \(y\) 使得 \(ax=my+b\)，即 \(ax-my=b\)，那么由裴蜀定理可知 \(b\) 为 \(gcd(a,m)\) 的倍数时才有整数解。

模板题AcWing 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≤10^5,1≤a_i,b_i,m_i≤2×10^9\)。

输入样例
22 3 64 3 5
输出样例
impossible-3
C++代码
#include using namespace std;typedef long long LL;int n;int exgcd(int a, int b, int &x, int &y){    if(!b)    {        x = 1, y = 0;        return a;    }    int d = exgcd(b, a % b, y, x);    y -= a / b * x;    return d;}int main(){    scanf("%d", &n);    while(n --)    {        int a, b, m, x, y;        scanf("%d%d%d", &a, &b, &m);        int d = exgcd(a, m, x, y);        if(b % d) puts("impossible");        else printf("%d\n", (LL)b / d * x % m);    }    return 0;}

关键词： 欧几里得算法 输入格式 满足条件