扩展欧几里得（模板）

佚名 4年前 (2020-02-05) 算法 1828人围观抢沙发百度已收录

斐蜀定理：

对于任意的正整数a，b，一定存在非零整数x，y，使得ax+by=gcd（a，b）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

扩展欧几里得算法用于求任意一对x和y

给定nn对正整数a,b，对于每对数，求出一组x,y，使其满足a∗x+b∗y=gcd(a,b)

代码：

import java.util.*;

 public class Main{
         static int x,y;
         static int exgcd(int a,int b){
                 if(b==0){
                     x=1; 
                     y=0;
                     return a;
                 }
                 int d = exgcd(b,a%b);
                 int t=x;
                 x=y;
                 y=t-a/b*y;
                 return d;
         }
         public static void main(String[] args) {
                 Scanner scan=new Scanner(System.in);
                 int t=scan.nextInt();
                 while(t-->0){
                         int a=scan.nextInt();
                         int b=scan.nextInt();
                         exgcd(a,b);
                         System.out.println(x+" "+y);
                 }
         }
 }