首页 > 其他分享 >扩展欧几里得

扩展欧几里得

时间:2023-11-19 09:12:08浏览次数:37  
标签:return gcd int 欧几里得 扩展 exgcd y1 x1


/*
    "数学的恐怖qwq"
    想了半天终于明白了, 这里尽量通俗的写出来
    扩展欧几里得算法有很多版本
    这里写两个, 选择喜欢的使用
    
    扩欧可以解决两项未知解, 具体原理来自裴蜀定理
    裴蜀定理:设 a,b 是不全为零的整数, 则存在整数 x,y, 使得 ax+by=gcd(a,b).
    而扩欧就可以在求出gcd的过程中把其中的x和y求出来(一种方案)
    就可以得到式子ax + by = gcd(a, b);中所有的数值
    因为知道了gcd(a, b)就可以通过这样求出每个二元一次方程组的一个解
    例如已知a, b, c, 求满足ax + by = c中想x, y的一个解
    通过扩欧可以求出a*x1 + b*y1 = gcd(a, b);
    这个式子左右两边都乘上c / gcd(a, b);
    就可以得到a*x2 + b*y2 = c; 这时候x2和y2我们知道, 而这就是ax + by = c的一个解
    通过这个还可以求逆元
    
    而具体实现
    普通欧几里得如下
    int gcd(int a, int b)
    {
        return b ? gcd(b, a % b) : a;
    }
    
    或者应该这样
    int gcd(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
        int d = gcd(b, a % b);
        return d;
    }
    
    我们可以多带两个值x, y, 因为递归下一层内的数组没法直接传上来, 这里就通过引用的方式, 
    取址传上来, 不是取值
    就变成
    int ecgcd(int a, int b, int &x, int &y)
    {
        if (b == 0)
        {
            return a;
        }
        int d = ecgcd(b, a % b, ?, ?); // 这两个问号下面会补上
        return d;
    }
    那俩问号暂且不管
    
    那么问题来了, 怎么求x, y, 
    首先你要知道, 只有一个等式是无法求出二元一次方程的唯一解的
    所以我们的解有无穷个, 而对于最后终止的那里, 也就是b == 0的情况
    ax + by = d, 因为b == 0, 所以a = d(为什么见普通欧几里得), 
    所以x = 1, 这样就确定了x, 但是y是可以变化的, 这也是为什么有无数解的原因
    因此这里的y可以随便去一个, 通常选y = 0(为什么下面会说),
    
    // 请把所有的x和y看成未知数, 不要想位置关系, 这里只是为了方便
    
    那么终止的x, y选完了, 接着就是看看怎么把x和y带回去
    原式子是ax + by = d; (1)
    它的递归下一层就是b*y1 + a%b * x1 == d (2)
    a % b == a - a/b * b (3)
    由(1)(3)可得 (a%b + a/b * b)*x + by = d (4)
    化简得 a%b * x + b(y + a/b * x) = d (5)
    通过(2)和(5) 可以发现, x1 = x, y1 = y + a/b * b (6)
    y = y1 - a/b * x, x = x1; (7)
    
    而x1和y1就是我想通过x和y传回来的值, 这时候看看上面两个问号, 就有两种填法
    ecgcd(b, a % b, x, y) 和 ecgcd(b, a % b, y, x)
    
    如果是ecgcd(b, a % b, x, y)
    那么本次递归ax + by = d, 下次b * x2 + a%b * y2 = d; 注意这里和(2)不一样
    传回来的x = x2 = y1, y = y2 = x1; 注意这里x和y数值上是下一层递归里面传上来的
    根据 y = y1 - a/b * x, x = x1; (7) 可得
    本次递归里的y = 下个递归里的x2 - 本次的a/b * 本次的x, 本次的x = 下次的y2
    而在实现上就是int t = y; y = x - a / b * t; x = t;
    这里有点难懂, 要注意x和y数值上是下一层递归里面传上来的, 用的还是本次递归的x, y
    作为容器, 我们要利用x, y, 更改他们自己
    
    具体代码就是
    int exgcd(int a, int b, int &x, int &y)
    {
        if (b == 0)
        {
            x = 1;
            y = 0;
            return a;
        }
        int d = exgcd(b, a % b, x, y);
        int t = y;
        y = x - a / b * t;
        x = t;
        return d;
    }
    
    如果是如果是ecgcd(b, a % b, y, x)
    那么本次递归ax + by = d, 下次b * y3 + a%b * x3 = d; // 这里的x3 y3都是未知数, 没什么具体含义, 所有的关系就是下面的那一句话
    传回来的y = y3 = y1, x = x3 = x1;
    根据 y = y1 - a/b * x, x = x1; (7) 可得
    本次的y = 下次的y3 - 本次的a/b * 本次的x, 本次的x = 下次的x3
    实现就是 y = y - a / b * x, x = x ==> y -= a / b * x; 
    唉?这时候我们传上来的x恰好等于这次的x, x就不用动了
    y的话就相当于自减, 非常巧妙
    
    实现
    int exgcd(int a, int b, int &x, int &y)
    {
        if (b == 0)
        {
            x = 1;
            y = 0;
            return a;
        }
        int d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    
    到这里就解释的差不多了, 注意=的关系, 
    
    b == 0时最好y = 0, 因为我们会把y传回去, 他会经历一系列变化
    取0的话可以防止出现int爆炸的情况, 不然你可以试试这题y = 100
    至此此题结束
    
*/
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;

// int exgcd(int a, int b, int &x, int &y)
// {
//     if (b == 0)
//     {
//         x = 1;
//         y = 0;
//         return a;
//     }
//     int d = exgcd(b, a % b, x, y);
//     int t = y;
//     y = x - a / b * t;
//     x = t;
//     return d;
// }

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int x, y;
        scanf("%d%d", &n, &m);
        exgcd(n, m, x, y);
        printf("%d %d\n", x, y);
    }
    
    return 0;
}

求逆元

什么是逆元, 逆元就是形如 a * x ≡ 1 (mod p) 其中x就叫做a对于p的一个逆元
相对的a就是x关于p的一个逆元

知道了定义 a * x ≡ 1 (mod p) 这个式子我们可以把他展开
变成a * x + p * y = 1 (y是任意整数)
这个式子形如 ax + by = d
所以这个式子可以用exgcd进行求解
也就是求出里面的x

求逆元还有一种方法, 也是一种特殊的情况, 当且仅当p为质数且(a, p) = 1
这时候它满足费马小定理 :如果p是一个质数,而整数a不是p的倍数,
也就是当且仅当p为质数且(a, p) = 1, 则有a ^ (p - 1) ≡ 1 (mod p)
这时候x也就是a的逆元就是a ^ (p - 2) ,
而这个东西可以通过快速幂求解
这就是逆元的特殊求法

欧拉定理 & 费马小定理 - OI Wiki (oi-wiki.org)

[[ecgcd通解]]

标签:return,gcd,int,欧几里得,扩展,exgcd,y1,x1
From: https://www.cnblogs.com/blind5883/p/17841589.html

相关文章

  • C#扩展方法
    定义扩展方法-C#编程指南-C#|MicrosoftLearn扩展方法使你能够向现有类型“添加”方法,而无需创建新的派生类型、重新编译或以其他方式修改原始类型。扩展方法是一种静态方法,但可以像扩展类型上的实例方法一样进行调用。对于用C#、F#和VisualBasic编写的客户端代码......
  • session源码、闪现、请求扩展
    session源码'''1app.session_interface默认是某个类的对象,以后全局对象session,就是SecureCookieSessionInterface()的对象2请求来了,会执行这个对象的:open_session方法3请求走了,会执行这个对象的:save_session方法4找出上面讲的--》读源码--》app.run()---->run_simp......
  • session源码,闪现,请求扩展
    1session源码......
  • 前端应该如何封装高扩展的axios请求库
    我看了很多axios的封装,但是我感觉他们的封装。也不够自由,主要是写完之后,如果以后有东西需要修改的时候,还要回去拦截器进行修改。但是有一些东西拦截器可能是你以后的业务需求才需要添加的。我就在想我能不能拦截器做成插件式的模式进行动态配置呢?例如下面的效果,点击添加一个请......
  • vue2.0源码简读(5. 扩展)
    5.1event平时开发工作中,处理组件间的通讯,原生的交互,都离不开事件。对于一个组件元素,不仅仅可以绑定原生的DOM事件,还可以绑定自定义事件,非常灵活和方便。那么接下来从源码角度来看看它的实现原理。为了更加直观,通过一个例子来分析它的实现:letChild={template:'<button......
  • php编译安装扩展
    1、linux下安装php的redis扩展wgethttps://codeload.github.com/edtechd/phpredis/zip/php7unzipphp7cdphpredis-php7phpize//如果不存在,就找phpize路径执行./configure--with-php-config=/usr/local/php/bin/php-config//php-config路径make&&make......
  • [WPF]标记扩展(Markup Extension)
    XAML是基于XML的语言,其遵循并扩展了XML的语法规则。其中一项扩展就是标记扩展(MarkupExtension),比如我们经常使用的绑定Binding和x:Type。什么是标记扩展标记扩展允许在XAML标记中使用特殊的语法来动态地为特性(Attribute)赋值或执行其他操作。简单来说,在XAML中,所有为XAML元素特......
  • 基于pybind11实现C++程序中调用Python脚本增加C++程序扩展性
     文章目录前言一、pybind11与Python环境配置二、C++环境配置三、C++调用Python交互代码四、C++调用PythonDemo完整源码 前言Windows平台,在实际C++项目开发中,结合pybind11库,让python成为C++的脚本语言,可以大大提高C++程序的可扩展性,大大提高开发效率,特别......
  • Net 高级调试之九:SOSEX 扩展命令介绍
    一、介绍今天是《Net高级调试》的第九篇文章。这篇文章设计的内容挺多的,比如:扩展的断点支持,如何查找元数据,栈回溯,对象检查,死锁检测等等,内容挺多的。功能特别强大,使用特别方便,但是需要说明一点,这些功能不是SOS的功能,是SOSEX的扩展功能,但是,这一系列功能只是支持NetFr......
  • 基于ABP的AppUser对象扩展
     在ABP中AppUser表的数据字段是有限的,现在有个场景是和老系统用户对接,需要在AppUser表中添加一个UId和IMId字段。本文以AppUser表扩展UId和IMId字段为例进行介绍。一.在Abp默认解决方案Test.Identity.EntityFrameworkCore更改IdentityEfCoreEntityExtensionMappings类,该操作......