借鉴

exgcd

//ax + by = 1
//x = x0 + kb
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong();
        long[] x = new long[1], y = new long[1];
        exgcd(a, b, x, y);
        long ans = x[0];
        System.out.println(((ans % b) + b) % b);
    }

    static long exgcd(long a, long b, long[] x, long[] y) {
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        long d = exgcd(b, a % b, y, x);
        y[0] -= a / b * x[0];
        //这里不能换位置，因为a / b会出现精度问题，如果把x[0]放前面可能会出现y偏大
        return d;
    }
}

gcd应用题