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。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f
#define MAXN 500010
const int MOD=1e9+7;
typedef long long ll;
using namespace std;
ll ext_gcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll r = ext_gcd(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t-(a/b)*y;
    return r;
}
int main()
{
    ll n, m, x, y, l, k, p;
    cin >> x >> y >> m >> n >> l;
    ll r = ext_gcd(n-m, l, k, p);//k和p為任意解，非最優 
    if((x-y)%r!=0){
        cout << "Impossible" << endl;
    }
    else{
        ll t = l/r;//k每次轉移量 
        ll ans = k*(x-y)/r;//從擴展歐幾里得標準公式轉到我們所列公式求得的k值
        cout << (ans%t+t)%t << endl;
    }
    return 0;
}

?