裴蜀定理

$$ 对于任意一对正整数a,b，一定存在非零整数x,y使得ax+by = (a,b) $$

$$ 可以用来判断方程ax+by=c是否有解，只要看c是否是(a,b)的倍数 $$

$$ 证明：已知(a,b)|(ax+by)所以c一定是(a,b)的倍数 $$

扩展欧几里得算法

$$ 给定一对正整数a，b，需要构造出a，b的系数：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 tmp = x;
        x = y;
        y = tmp - a / b * y;
        return d;
    }

$$ 证明：当b=0时，我们需要构造ax+by=(a,b)\iff ax+0=(a,0)=a $$

$$ 即可令x=1，y=0 $$

$$ 当b!=0时，可知进行完exgcd(b,a mod b)的递归结果有 $$

$$ bx+(amodb)y=(a,b) $$

$$ \iff bx+(a-\lfloor\frac{a}{b}\rfloor)y=(a,b) $$

$$ \iff ay+b(x - \lfloor\frac{a}{b}\rfloor y)=(a,b) $$

$$ 所以此时x=y,y = x - \lfloor\frac{a}{b}\rfloor y $$

线性同余方程

$$ 给定a,b,m构造出x使得ax\equiv b(modm)成立 $$

$$ ax\equiv b(modm)\iff ax = my+b(y是整数) $$

$$ 由此可知ax-my=b $$

$$ 令y_2=-y则有ax+my_2=b $$

$$ 则构造x一定使得ax+my_2=b有解 $$

$$ 根据裴蜀定理可知该方程有解的充要条件是(a,b)|b $$

$$ 设d=(a,b),若d\nmid b则x不存在 $$

$$ 若d|b，则我们可以用扩展欧几里得算法算出ai+bj=d的i，j $$

$$ 在将i\times \frac{b}{d},j\times \frac{b}{d}得到x与y_2 $$

AcWing 877. 扩展欧几里得算法 原题链接

给定nn对正整数ai,biai,bi，对于每对数，求出一组xi,yixi,yi，使其满足ai∗xi+bi∗yi=gcd(ai,bi)ai∗xi+bi∗yi=gcd(ai,bi)。

输入格式

第一行包含整数n。

接下来n行，每行包含两个整数ai,biai,bi。

输出格式

输出共n行，对于每组ai,biai,bi，求出一组满足条件的xi,yixi,yi，每组结果占一行。

本题答案不唯一，输出任意满足条件的xi,yixi,yi均可。

数据范围

1≤n≤1051≤n≤105,
1≤ai,bi≤2∗1091≤ai,bi≤2∗109

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

    static long x;
    static long y;
    public static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long d = exgcd(b, a % b);
        long tmp = x;
        x = y;
        y = tmp - a / b * y;
        return d;
    }
    public static void main(String[] args) {
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            long d = exgcd(a, b);
            out.println(x + " " + y);
        }
        out.flush();
        out.close();
    }

AcWing 878. 线性同余方程 原题链接

给定nn组数据ai,bi,miai,bi,mi，对于每组数求出一个xixi，使其满足ai∗xi≡bi(mod mi)ai∗xi≡bi(mod mi)，如果无解则输出impossible。

输入格式

第一行包含整数nn。

接下来nn行，每行包含一组数据ai,bi,miai,bi,mi。

输出格式

输出共n行，每组数据输出一个整数表示一个满足条件的xixi，如果无解则输出impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在int范围之内。

数据范围

1≤n≤1051≤n≤105,
1≤ai,bi,mi≤2∗1091≤ai,bi,mi≤2∗109

输入样例：

2
2 3 6
4 3 5

输出样例：

impossible
-3

    static int x;
    static int 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 tmp = x;
        x = y;
        y = tmp - a / b * y;
        return d;
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int m = in.nextInt();
            int d = exgcd(a, m);
            if (b % d != 0) {
                out.println("impossible");
            }else {
                long res = (long) x * (b / d);
                out.println(res % m);
            }
        }
        out.flush();
        out.close();
    }