Bzoj 1477(扩展欧几里得算法解不定方程)

BZOJ 1477
luogu免权限地址
扩展欧几里得算法,由题可列$(x+m*t)\equiv (y+n*t)\pmod L$,其中$t$为所求
由同余性质得:$(x+m*t)-(y+n*t)=Lk$
变形得:$(n-m)t+lk=x-y$,则转换为$ax+by=c$的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL x, y, m, n, L;
LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
LL abss(LL a) {return a >= 0 ? a : -a;}
void exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b, x, y);
int tmp = x;
x = y, y = tmp - a / b * y;
}
void clean() {}
void solve() {
clean();
LL xi = m - n, yi = L, c = y - x, g = gcd(xi, yi);
if (c % g != 0) {printf("Impossible\n"); return ;}
c /= g;
LL a, b;
exgcd(xi, yi, a, b);
yi /= g, yi = abss(yi);
a = ((a * c + yi) % yi + yi) % yi;//必须mod yi(b / gcd)
printf("%lld\n", a);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L), solve();
return 0;
}

------ 本文结束 ------