AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

扩展欧几里得算法

作者: 作者的头像   cyuyu ,  2022-01-15 00:04:10 ,  所有人可见 ,  阅读 86


1


扩展欧几里得算法:

裴蜀定理:

对于a,b总是存在非零整数x,y使得 ax + by = (a , b)
证明:
因为a,b两者的最大公约数是(a,b)=d的,所以ax+by的最大公约数也是d,所以会存在x,y使得两者相等

代码:

#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else{

        int d= exgcd(b,a%b,y,x);  //注意这里****
         y=y-a/b*x;              //*************,X,y这样的变换关系只进行一次,所以
                                 //不可以写为y=y-a/b*x; 
                                 //     return exgcd(b,a%b,y,x);
        return d;
    }
}
int main(){
    int n;
    cin>>n;
    int x,y,a,b;
    while(n--){
        cin>>a>>b;
        int c=exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }

    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息