5-扩展欧几里得算法

算法思想

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    static int x, y;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while(n -- > 0)
        {
            int a = in.nextInt(),
                b = in.nextInt();
            exgcd(a, b);
            System.out.println(x + " " + y);
        }
    }
    
    public static int exgcd(int a, int b)
    {
        if(b == 0)
        {
            x = 1; y = 0;
            return a;
        }
        int d = exgcd(b, a % b);
        // 由裴蜀定理和欧几里得算法推导出下述公式
        int x1 = x;
        int y1 = y;
        x = y1;
        y = x1 - a / b * y1;
        return d;
    }
}

参考资料

1. G16 裴蜀定理_哔哩哔哩_bilibili
2. G17 不定方程 扩展欧几里得算法_哔哩哔哩_bilibili