拡張ユークリッドpoj 1061カエルのデート

拡張ユークリッドはとてもクラシックですが、時には使いにくいこともあります.何かが急に分からない.の
そこで逆天テンプレートが来ました.のAx+By=Cがリストされていれば、x>=boundの一連の解を解くことができます~

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    LL r = exgcd(b, a % b, x, y);
    LL t = y;
    y = x - a / b * y;
    x = t;
    return r;
}

/*    x>=bound  x y，  true    
    ，               ~
           ，          ，  a b       0~*/
bool solve(LL a, LL b, LL c, LL bound, LL &x, LL &y) {
    LL xx, yy, d = exgcd(a, b, xx, yy);
    if(c % d) return false;

    xx = xx * c / d; yy = yy * c / d;
    LL t = (bound - xx) * d / b;

    x = xx + b / d * t;
    if(x < bound) {
        t++;
        x = xx + b / d * t;
    }
    y = yy - a / d * t;
    return true;
}

この問題について、私たちは
A=n-m,B=L,C=x-y
Aの正負性と0かどうかに注意して、それから直接テンプレートをセットして、次はテンプレートの例です.

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MX = 3e4 + 5;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    LL r = exgcd(b, a % b, x, y);
    LL t = y;
    y = x - a / b * y;
    x = t;
    return r;
}

/*    x>=bound  x y，  true    
    ，               ~
           ，          ，  a b       0~*/
bool solve(LL a, LL b, LL c, LL bound, LL &x, LL &y) {
    LL xx, yy, d = exgcd(a, b, xx, yy);
    if(c % d) return false;

    xx = xx * c / d; yy = yy * c / d;
    LL t = (bound - xx) * d / b;

    x = xx + b / d * t;
    if(x < bound) {
        t++;
        x = xx + b / d * t;
    }
    y = yy - a / d * t;
    return true;
}

int main() {
    LL x, y, m, n, L;
    LL A, B, C, X, Y;
    while(~scanf("%I64d%I64d%I64d%I64d%I64d", &x, &y, &m, &n, &L)) {
        A = n - m; B = L; C = x - y;
        if(A == 0) { //  solve         
            printf("Impossible
");
            continue;
        }
        if(A < 0) A = -A, C = -C; //  A B    
        if(solve(A, B, C, 0, X, Y)) { //   x >=1,      0，         ，   0 1   
            printf("%I64d
", X); // ，，    ，，   ！
        } else {
            printf("Impossible
");
        }
    }
    return 0;
}