斐蜀定理：
對于任意的正整數a，b，一定存在非零整數x，y，使得ax+by=gcd（a，b）
擴展歐幾里得演算法用于求任意一對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); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93560.html
標籤：其他
上一篇：乘法逆元（模板）