题目 给定两个整数 \(a,c,m\) 请求出模方程
\[ax\equiv c\pmod m\tag{1}
\]
的最小正整数解。
分析 我们构造方程
\[ax\equiv 1\pmod m\tag{2}
\]
不难发现，如果我们能求出 \((2)\) 中的一个解，将其乘上 \(c\) 即可得到 \((1)\) 的一个解。那么现在就要求 \((2)\) 的一个解。其等价于不定方程
\[ax+my=1\tag{3}
\]
我们构造
\[mx+(a\%m)y=1\tag{4}
\]
它等价于
\[mx+(a-a/m\cdot m)y=1\tag{5}
\]
其中"/"是整除。
不难发现，如果我们知道 \((5)\) 的一个解 \(x_0,y_0\)，则有\(y_0,x_0-a/m\cdot y\) 是 \((3)\) 的一个解，其中"/"是整除。边界条件为 \(m=0\) 时 \(x=1,y=0\)，所以可以递归求解。
假定我们知道了 \((2)\)（也即\((3)\)）的一组解 \(x_0,y_0\) 则 \(c\cdot x_0\) 为 \((1)\) 的一个解，所以 \(c\cdot x_0\%\frac{m}{GCD(a,m)}\) 为 \((1)\) 的最小正整数解（为什么？）。
例题 青蛙的约会
分析 即求
\[x+k\cdot m \equiv y + k\cdot n \pmod l
\]
的最小正整数解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, y, m, n, l;
ll exgcd(ll a, ll b, ll& x, ll& y)
{
if (!b) return x = 1, y = 0, a;
ll d = exgcd(b, a % b, y, x);
return y -= a / b * x, d;
}
int main()
{
while (~scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l)) {
if (n < m) swap(n, m), swap(x, y);
ll X = 0, Y = 0;
ll d = exgcd(n - m, l, X, Y), r = l / d;
if ((x - y) % d) puts("Impossible");
else printf("%lld\n", ((x - y) / d * X % r + r) % r);
}
}