[luoguP1516] 青蛙的约会（扩展欧几里得）

传送门

对于数论只会gcd的我，也要下定决心补数论了

列出方程

(x + t * m) % l = (y + t * n) % l

那么假设这两个式子之间相差 num 个 l，即为

x + t * m = y + t * n + num * l

经过化简得

(n - m) * t + l * num = x - y

那么可以用扩展欧几里得求出结果

——代码

#include <cstdio>

#define LL long long

inline void exgcd(LL a, LL b, LL &d, LL &x, LL &y)

{

	if(!b) d = a, x = 1, y = 0;

	else exgcd(b, a % b, d, y, x), y -= x * (a / b);

}

int main()

{

	LL x, y, m, n, l, d, t, num;

	scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l);

	if(n - m < 0) x ^= y ^= x ^= y, n ^= m ^= n ^= m;

	exgcd(n - m, l, d, t, num);

	if((x - y) % d) puts("Impossible");

	else l = l / d, printf("%lld\n", ((x - y) / d * t % l + l) % l);

	return 0;

}

巴特西

[luoguP1516] 青蛙的约会（扩展欧几里得）

最新文章

热门文章