算法基础之扩展欧几里得算法

2023-12-22 17:46:04

扩展欧几里得算法

  • 核心思想:裴蜀定理 :

    • 在这里插入图片描述

    • 欧几里得算法: 辗转相除法求最大公约数

    • 在这里插入图片描述

      • 传入参数(int a,int b,int &x,int &y)

      • 递归(int b,int a%b,int y,int x) xy换位置 方便计算(推公式)

      •   #include<iostream>
          #include<algorithm>
          
          using namespace std;
          const int N = 100010;
          
          int exgcd(int a,int b,int &x,int &y)
          {
              if(!b)  //b == 0 说明最深层 有且仅有一种xy取值
              {
                  x = 1 ,y = 0;
                  return a;
              }
              else
              {
                  int d = exgcd(b, a % b , y , x);  //递归
                  y -= a/b * x;  //由公式推出来 y的值
                  return d;  //return exgcd();
              }
          }
          
          int main()
          {
              int n;
              cin>>n;
              
              while(n--)
              {
                  int a,b,x,y;
                  scanf("%d %d", &a, &b);
                  exgcd(a,b,x,y);
                  printf("%d %d\n", x,y);
              }
          }
        

文章来源:https://blog.csdn.net/Pisasama/article/details/135157305
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。