欧几里得_综合

欧几里得扩张模板

/*** 扩展欧几里得算法模板* x=k1* y=x1-a/b*k1*/
public class f扩展欧几里得 {static long x;//储存axstatic long y;//储存by
public static void main(String[] args) {     try {//2x+7y=1long f=linearEquation(3,9,6);System.out.println(f);//最大公约数System.out.println(x+" "+y);} catch (Exception e) {// TODO Auto-generated catch blocke.printStackTrace();}
}
private static long ext_gcd(long a, long b) {// TODO Auto-generated method stubif(b==0) {//初始化x=1;y=0;return a;}long  res=ext_gcd(b,a%b);//最大公约数 res=along x1=x;//备份 上一个的 x=y;//更新x // 0=x==y=0 1到了 1x+0b=1底层 然后层层返回 a 0 =1 y=x1-a/b*y;//更新y 0=y==1-上次的a/b*0；return res;//返回最大公约数，和x,y
}
/*** 线性方程* ax+by=m 当m时gcd(a,b)倍数时有解* 等价于ax = m mod b*/
public static long linearEquation(long a,long b,long m)throws Exception {long d=ext_gcd(a, b);//返回一个公约数if(m%d!=0) {throw new Exception("无解");//抛异常}long n=m/d;//约一下，考虑m是d的倍数x*=n;y*=n;return d;//返回最大公约数
}
}