扩展欧几里得补档

Posted on | In , ,

POJ – 1061 青蛙的约会

思路：
不能直接暴力，看网上的题解说这道题卡了使用mod的运行时间。所以要使用extgcd。方程由mt+x=kl+nt+y推出得到(m-n)t-k*l=y-x计算这个方程即可

代码：

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
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 1e9
#define ll long long
#define ms(a) memset(a,0,sizeof(a))

using namespace std;
ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a%b, y, x);
        y -= (a / b)*x;
    }
    else {
        x = 1, y = 0;
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
    ll x,y,m,n,l;
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    while (cin>>x>>y>>m>>n>>l) {
        ll x1, y1;
        ll gcds = extgcd(m - n, -l, x1, y1);
        if ((y - x) % gcds != 0) {
            cout << "Impossible" << "\n";
        }
        else {
            x1 = x1*(y - x) / gcds;
            ll t = l / gcds;
            t = t > 0 ? t : -t;
            if (x1 >= 0)
                x1 = x1%t;
            else
                x1 = x1%t + t;
            cout << x1 << endl;
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

UVA-10104 Euclid Problem

代码：

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#pragma warning(disable : 4996)
#define INF 1e9
#define ll long long
#define ms(a) memset(a,0,sizeof(a))

using namespace std;
ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll d = a;
    if (b == 0) {
        x = 1, y = 0;
    }
    else {
        d = extgcd(b, a%b, y, x);
        y -= (a / b)*x;
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
    ll a,b;
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    while (cin>>a>>b) {
        ll x, y, gcds;
        gcds = extgcd(a, b, x, y);
        cout << x << " " << y << " " << gcds << "\n";
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}