使用裴蜀公式来求解线性方程组的第一个大于零的解

1. 假设方程组卫ax + by = m

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：

ax + by = m

有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。

例如，12和42的最大公因子是6，则方程12x + 42y = 6有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。

特别来说，方程 ax + by = 1 有解当且仅当整数a和b互素。

裴蜀等式也可以用来给最大公约数定义：d其实就是最小的可以写成ax + by形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理

使用裴蜀公式来求解线性方程组的第一个大于零的解

所以在求解两个数的最大公约数的时候不断更新x和y，当求出的解x小于零的时候通过循环加上B的倍数那么就可以得到第一个大于零的解

	A'x'+B'y'+(u+(-u))A'B'=1
=>	(x' + uB')*A' + (y' - uA')*B' = 1
=>	X = x' + uB', Y = y' - uA'

2.代码如下：
import java.util.Scanner;
public class Main{
   static long x;
   static long y;
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       long A = sc.nextLong();
       long B = sc.nextLong();
       long C = sc.nextLong();
       long res;
       try {
           res = linearEquation(A, B, C);
           System.out.println(" x = " + res);
       } catch (Exception e) {
           System.out.println("无解");
       }
   }

   public 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 x1 = x;
       x = y;
       y = x1 - (A / B) * y;
       return res;
   }

   public static long linearEquation(long A, long B, long C) throws Exception{
       long d = ext_gcd(A, B);
       if(C % d != 0){
           throw new Exception("无解");
       }
       A /= d;
       B /= d;
       C /= d;
       x *= C;
       //通解求出第一个大于零的解
//       A'x'+B'y'+(u+(-u))A'B'=1
//               =>   (x' + uB')*A' + (y' - uA')*B' = 1
//               =>   X = x' + uB', Y = y' - uA'
       while(x < 0){
           x += B;
       }
       y = (C - A * x) / B;
       System.out.print("y = " +y);
       return x;
   }
}

使用裴蜀公式来求解线性方程组的第一个大于零的解

相关推荐