裴蜀定理
扩展欧几里得算法
线性同余方程
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();
}