求公因数的本质——扩展欧几里得算法,递归逼近,反正又是一个不打算弄懂的东西,记个模板顶多了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| import java.util.*; public class Main { static long x,y,r; public static void main(String[] args) { Scanner sc= new Scanner(System.in); while(sc.hasNext()){ long a=sc.nextInt(); long b=sc.nextInt(); System.out.println(gcd(a,b)); exgcd(a,b); System.out.println(x+"*"+a+y+"*"+b+"="+r); } } static long gcd (long a,long b){ return a==0?b:gcd(b%a,a); } static void exgcd(long a,long b){ if(b==0){ x=1; y=0; r=a; } else{ exgcd(b,a%b); long temp=x; x=y; y=temp-(a/b)*y; } } }
|