首页 > 编程语言 >扩展欧几里得算法

扩展欧几里得算法

时间:2022-11-07 15:36:28浏览次数:46  
标签:return gcd int 欧几里得 扩展 exgcd 算法 y1 x1


题目:

扩展欧几里得算法_#include

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
if(b==0)
{
x = 1, y = 0;
return a;
}
int x1,y1,gcd;
gcd = exgcd(b, a%b, x1, y1);
x = y1, y = x1 - a/b*y1;
return gcd;
}
int main()
{
int n,a,b,x,y;
cin>>n;
while(n--)
{
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
}


标签:return,gcd,int,欧几里得,扩展,exgcd,算法,y1,x1
From: https://blog.51cto.com/u_15866659/5829909

相关文章

  • 数据机构 最小生成树(Prim算法(普里姆、Kruskal算法( 克鲁斯卡尔))
    8.8、最小生成树连通图的生成树是包含图中全部顶点的一个极小连通子图;若图中顶点数为n,则它的生成树含有\(n-1\)条边。最小生成树对于一个带权连通无向图G=(V,E),生成树......
  • 非对称加密及RSA算法
    非对称加密及RSA算法 最近在学习区块链相关的知识,发现其保证去中心化的一个重要的手段就是基于密码学中的非对称加密。何为非对称加密?在回答这个问题之前,我觉得有比说一下......
  • 『数据结构与算法』解读递归算法!
    文章目录​​一.什么是递归​​​​1.1.递归的定义​​​​1.2.何时使用递归​​​​1.3.递归模型​​​​二.递归算法的设计​​​​2.1.递归算法设计的步骤​​​​......
  • 实验二:逻辑回归算法实验
    实验二:逻辑回归算法实验【实验目的】1.理解逻辑回归算法原理,掌握逻辑回归算法框架;2.理解逻辑回归的sigmoid函数;3.理解逻辑回归的损失函数;4.针对特定应用场景及数据,能......
  • 实验二:逻辑回归算法实验
    实验二:逻辑回归算法实验班级:20大数据(3)班学号:201613341【实验目的】理解逻辑回归算法原理,掌握逻辑回归算法框架;理解逻辑回归的sigmoid函数;理解逻辑回归的损失函数;......
  • 实验二:逻辑回归算法实验
    【实验目的】1.理解逻辑回归算法原理,掌握逻辑回归算法框架;2.理解逻辑回归的sigmoid函数;3.理解逻辑回归的损失函数;4.针对特定应用场景及数据,能应用逻辑回归算法解决实际分......
  • 什么是体元?什么是体素?Marching Cubes算法理解
    Marchingcubesusesadivide-and-conquerapproachtolocatethesurfaceinalogicalcubecreatedfromeightpixels;foureachfromtwoadjacentslicesMarchin......
  • Nginx1.8.1 编译扩展https
    nginx无缝编译扩展https本贴只限用于通过编译安装的nginx,如果用的是yum源安装请卸载后参见 安装nginx部分。一、重新编译nginx1、查看nginx是否支持ssl/usr/local/nginx/sb......
  • 决策树算法 ----- 机器学习
                            ......
  • K均值聚类算法 ----- 机器学习(无监督学习)
         ......