「BZOJ 1477」青蛙的约会

题目大意：

设答案为 $k$，有

$$x+km \equiv y+kn \pmod L\\ k(n-m) \equiv (x-y) \pmod L$$

设 $n-m=a,L=b,x-y=c$，则问题即为求 $ax+by=c$ 的最小非负整数解

等式两边同时除以 $(a,b)$ 得

$$a'x+b'y=c'$$

可知 $(a’,b’)=1$，于是 $exgcd$ 求解

$$a'x'+b'y'=1$$

可知方程 $a’x+b’y=c’$ 的所有整数解为

$$x=c'x'+b't, y=c'y'-a't$$

则 $x$ 的最小非负整数解为 $c’x’\mod b’$

注意一个细节，如果 $a$ 小于 $0$，由于 $b$ 是大于 $0$ 的，那么 $(a,b)$ 就会小于 $0$，$b’=\dfrac{b}{(a,b)}$ 也会小于 $0$，那么最后 $x=(c’x’\mod b’+b’)\mod b’$ 就会小于 $0$ 了。因此在 $a<0$ 时，要将 $a,c$ 同时取相反数。

#include <cstdio>

typedef long long LL;
LL xx, yy, m, n, L, a, b, c, x, y, t;

LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

int main() {
    scanf("%lld%lld%lld%lld%lld", &xx, &yy, &m, &n, &L);
    a = n - m, b = L, c = xx - yy;
    if (a < 0) a = -a, c = -c;
    t = gcd(a, b);
    if (c % t) { puts("Impossible"); return 0; }
    a /= t, b /= t, c /= t;
    exgcd(a, b, x, y);
    x = (x * c % b + b) % b;
    if (x == 0) x = b;
    printf("%lld\n", x);
    return 0;
}

时间复杂度 $O()$