ACM专题学习|青蛙的约会--扩展欧几里得 c语言|算法|c++

ACM专题学习四
题目 artist 和小旋只在网上一起打过比赛，没有见过面。
开学返校了，他们决定出来约个饭，他们处于同一条长为L的轴线上，且这条轴线是头尾相连的
artist的初始坐标是X ，她顺时针走，每秒可以走m米
小旋的初始坐标是Y ，他也是顺时针走，每秒可以走n米
【ACM专题学习|青蛙的约会--扩展欧几里得】小旋和artist每秒都在走路。小旋想知道，他到底要走多少秒，才能遇见artist呢？
秒只能是整数秒，遇见的含义是到**同一个坐标**。
注意：这道题不支持bits/stdc++.h头文件！
输入输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
输出输出碰面所需要的秒数，如果永远不可能碰面则输出一行"Impossible"
样例输入

1 2 3 4 5

样例输出 4
分析轴线收尾相连，两只蛙蛙走相同的秒数能到达同一个位置，说明它们走的路程模L同余，
(x+mt)%L=(y+nt)%L,化为带余数的式子x+mt=aL+r,y+nt=bL+r,两式相减得（m-n)t+x-y=(a-b)L,
即（m-n)t-(a-b)L=y-x，其中t和k是变量，（m-n)t+kL=y-x，要求出t，用扩展欧几里得
扩欧求x,y的证明：
Ax + By = C = gcd(A, B)
∵ gcd(A, B) = gcd(B, A mod B)
∵ Bx’ + (A mod B)y’ = gcd(B, A mod B)
∴ Bx’ + (A mod B)y’ = gcd(A, B)
∴ Bx’ + (A - A/B * B)y’ = gcd(A, B)
→ Bx’ + Ay’ - B*(A/B)y’ = gcd(A, B)
→ Ay’ + B(x’ - (A/B)*y’) = gcd(A, B)
∴ x = y’, y = x’ -(A/B)*y’
利用递归就可以实现扩欧的运算
用int会WA，所以用long long

#include usingnamespacestd; longlongextgcd( longlonga,longlongb,longlong&x,longlong&y) { longlongd, t; if(b == 0) { x = 1; y = 0; returna; } d = extgcd(b, a % b, x, y); t = x - a / b * y; x = y; y = t; returnd; } intmain() { longlongx, y, m, n, L, t, k, d, r; while(cin >> x >> y >> m >> n >> L) { d = extgcd(n - m, L, t, k); r = L / d; if((x - y) % d) cout <<"Impossible"<< endl; else cout << ((x - y) / d * t % r + r) % r << endl; } return0; }