裴蜀定理

裴蜀定理.pdf

扩展欧几里得算法

时间复杂度O(logn)
求解裴蜀定理中x和y以及(a, b)的过程就是扩展欧几里得算法

扩欧算法递归过程.pdf

例题

877. 扩展欧几里得算法

给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 ai,bi。
输出格式
输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi,yi均可。
数据范围
1≤n≤105
1≤ai,bi≤2×109
输入样例：

  1. 2
  2. 4 6
  3. 8 18

输出样例：

  1. -1 1
  2. -2 1
  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  9.         while (n-- > 0) {
  10.             int a = sc.nextInt(), b = sc.nextInt();
  12.             int[] x = new int[1], y = new int[1];
  14.             exgcd(a, b, x, y);
  16.             System.out.println(x[0] + " " + y[0]);
  17.         }
  18.     }
  20.     static int exgcd(int a, int b, int[] x, int[] y) {
  21.         if (b == 0) {
  22.             x[0] = 1;
  23.             y[0] = 0;
  24.             return a;
  25.         }
  27.         int d = exgcd(b, a % b, y, x);
  29.         y[0] -= a / b * x[0];
  31.         return d;
  32.     }
  33. }

如何用扩展欧几里得算法求逆元？

例如给定a和b求a关于模b的乘法逆元。

答：直接用扩欧函数 int d = exgcd(a, b, x, y)
如果 d != 1 说明a和b不互质，乘法逆元不存在
如果 d == 1 说明a关于模b的乘法逆元存在，x就是a关于模b的乘法逆元

当然x只是某一个特解，范围不一定符合要求，将其转换为 [0, b) 范围中的解
x = (x + b) % b

特别注意：溢出处理