J

https://vjudge.net/contest/218366#problem/J

第一步追及公式要写对：y+nk-(x+mk)=pL => (n-m)k+lp=x-y

可以看出扩展欧几里得原型，这里注意扩展欧几里得求出的是任意解，非最优，要推出最小解k。

(n-m)x+ly=gcd => (n-m)(x*(x-y)/gcd) + l*y*(x-y)/gcd = x-y

则k = x*(x-y)/gcd（某一解非最小），由于k每次可转移t = l/gcd

最小解为(k%t+t)%t。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 #include<stack>
 9 #include<queue>
10 #define lson l, m, rt<<1
11 #define rson m+1, r, rt<<1|1
12 #define IO ios::sync_with_stdio(false);cin.tie(0);
13 #define INF 0x3f3f3f3f
14 #define MAXN 500010
15 const int MOD=1e9+7;
16 typedef long long ll;
17 using namespace std;
18 ll ext_gcd(ll a, ll b, ll &x, ll &y)
19 {
20     if(b == 0){
21         x = 1;
22         y = 0;
23         return a;
24     }
25     ll r = ext_gcd(b, a%b, x, y);
26     ll t = x;
27     x = y;
28     y = t-(a/b)*y;
29     return r;
30 }
31 int main()
32 {
33     ll n, m, x, y, l, k, p;
34     cin >> x >> y >> m >> n >> l;
35     ll r = ext_gcd(n-m, l, k, p);//k和p为任意解，非最优 
36     if((x-y)%r!=0){
37         cout << "Impossible" << endl;
38     }
39     else{
40         ll t = l/r;//k每次转移量 
41         ll ans = k*(x-y)/r;//从扩展欧几里得标准公式转到我们所列公式求得的k值
42         cout << (ans%t+t)%t << endl;
43     }
44     return 0;
45 }