JAVA算法:欧几里德算法(GCD)又称辗转相除法计算两个整数a,b的最大公约数(JAVA代码)
package com.bean.algorithmbasic;public class GDCDemo {/** 欧几里德算法(GCD)又称辗转相除法,用于计算两个整数a,b的最大公约数。* 基本思路:设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。* */public static int gcd(int a, int b) {if (b==0) {return a;}else {return gcd(b,a%b);}}/** 扩展算法* * 基本思路:对于不全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,* 必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。* * 证明:设 a>b。* 1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;* 2,ab!=0 时,设 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b);* 根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);* 则:ax1+by1=bx2&#