【ICPC模板】多元一次不定方程（丢番图方程）求解

106 阅读 0 评论 70 点赞

我是靠谱客的博主慈祥糖豆，这篇文章主要介绍【ICPC模板】多元一次不定方程（丢番图方程）求解，现在分享给大家，希望可以做个参考。

核心：

首先移项，左边仅剩下ax + by，使用扩展欧几里得求解x和y，其右侧值应当满足能够整除gcd(a, b)，接着用扩展gcd求解gcd(a, b)和c的参数，c的参数z将作为中间过程的答案，而gcd(a, b)的倍数将用来给前面求过的所有结果翻倍，以此类推。

方程有解当且仅当右侧常数c能够整除gcd(a, b, c, d……)。

代码：

复制代码

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

int ex_gcd(int a, int b, int &x, int &y) {
    int xp, xpp, yp, ypp;
    int r, q;
    q = a / b, r = a % b;
    xpp = x = 0, ypp = y = 1;
    if (!r) return b;
    xp = x = 1, yp = y = -q;
    while (true) {
        a = b, b = r;
        q = a / b, r = a % b;
        if (!r) return b;
        x = xpp - xp * q;
        y = ypp - yp * q;
        xpp = xp, ypp = yp;
        xp = x, yp = y;
    }
}

// 返回false表示无解
// 当所有元素的gcd无法整除常数c时，方程无整数解
const int LIM = 1e6 + 10;
int multi[LIM], ans[LIM], coefficient[LIM];
bool indeterEqualtion(int *coefficient, int *ans, int len, int c) {
    if (len == 1) {
        if (c % coefficient[0]) return false;
        ans[0] = c / coefficient[0];
        return true;
    }
    // init
    int g = ex_gcd(coefficient[0], coefficient[1], ans[0], ans[1]);
    for (int i = 2; i < len; i++)
        g = ex_gcd(g, coefficient[i], multi[i - 1], ans[i]);
    if (c % g) return false;
    int sufmul = 1;
    for (int i = len - 2; i; i--)
        sufmul *= multi[i], ans[i] *= sufmul;
    ans[0] *= sufmul;
    return true;
}

int main(void) {
    ios::sync_with_stdio(false);
    coefficient[0] = 155;
    coefficient[1] = 341;
    coefficient[2] = 385;
    indeterEqualtion(coefficient, ans, 3, 1);
    for (int i = 0; i < 3; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

int ex_gcd(int a, int b, int &x, int &y) {
    int xp, xpp, yp, ypp;
    int r, q;
    q = a / b, r = a % b;
    xpp = x = 0, ypp = y = 1;
    if (!r) return b;
    xp = x = 1, yp = y = -q;
    while (true) {
        a = b, b = r;
        q = a / b, r = a % b;
        if (!r) return b;
        x = xpp - xp * q;
        y = ypp - yp * q;
        xpp = xp, ypp = yp;
        xp = x, yp = y;
    }
}

// 返回false表示无解
// 当所有元素的gcd无法整除常数c时，方程无整数解
const int LIM = 1e6 + 10;
int multi[LIM], ans[LIM], coefficient[LIM];
bool indeterEqualtion(int *coefficient, int *ans, int len, int c) {
    if (len == 1) {
        if (c % coefficient[0]) return false;
        ans[0] = c / coefficient[0];
        return true;
    }
    // init
    int g = ex_gcd(coefficient[0], coefficient[1], ans[0], ans[1]);
    for (int i = 2; i < len; i++)
        g = ex_gcd(g, coefficient[i], multi[i - 1], ans[i]);
    if (c % g) return false;
    int sufmul = 1;
    for (int i = len - 2; i; i--)
        sufmul *= multi[i], ans[i] *= sufmul;
    ans[0] *= sufmul;
    return true;
}

int main(void) {
    ios::sync_with_stdio(false);
    coefficient[0] = 155;
    coefficient[1] = 341;
    coefficient[2] = 385;
    indeterEqualtion(coefficient, ans, 3, 1);
    for (int i = 0; i < 3; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << endl;
    return 0;
}