[LanQiao]一步之遥

26
2019/07

# [LanQiao]一步之遥

## 思路1：暴力，非常简单

volence(97,-127);

private static void violence(long f, long b) {
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
if(i*f+j*b==1){
System.out.println(i+" "+j);
return;
}
}
}
}                                                 

## 思路2：扩展欧几里得算法

【扩展欧几里得算法是用来在已知a,b求解一组x,y,使它们满足贝祖等式：ax + by = gcd(a,b) = d(解一定存在，根据数论中的相关定理)】

package BlueCup.Six_MathQuestion;

public class 一步之遥 {
public static void main(String[] args) {
//97*x-127*y=1;
long F=97;
long B=-127;
try {
LinearEquation(F,B,1);
System.out.println(x+" "+y);
}catch (Exception e){
System.out.println(e.getMessage());
}
}
private static void LinearEquation(long a, long b, long m)throws Exception {
long d=ext_gcd(a,b);
if(m%d!=0)throw new Exception("无解");
long t=m/d;
x*=t;
y*=t;
}
static long x,y;
private static long ext_gcd(long a, long b) {
if(b==0){
x=1;
y=0;
return a;
}
long res=ext_gcd(b,a%b);
long x0=x;
x=y;
y=x0-a/b*y;
return res;
}
}                                                                                 

百度已收录

Last modification：July 31st, 2019 at 12:16 pm