GESP二级 - 不定方程求解 - C++ 代码实现

GESP二级 - 不定方程求解 - C++ 代码实现

问题描述

给定正整数 a，b，c。求不定方程 ax + by = c 关于未知数 x 和 y 的所有非负整数解组数。

输入描述

一行，包含三个正整数 a，b，c，两个整数之间用单个空格隔开。每个数均不大于 1000。

输出描述

一个整数，即不定方程的非负整数解组数。

用例输入 1

2 3 18

用例输出 1

4

解题思路

根据裴蜀定理，对于不定方程 ax + by = c，当且仅当 c 是 a 和 b 的最大公约数的倍数时，方程有整数解。

因此，首先需要计算 a 和 b 的最大公约数，然后判断 c 是否是最大公约数的倍数。

若是最大公约数的倍数，则存在整数解。

接下来，可以使用枚举的方法，遍历 x 的取值范围 [0, c/a]，计算 y 的取值，判断是否满足方程。统计满足方程的组数即可。

具体步骤

1. 读入 a、b、c 三个整数。
2. 计算 a 和 b 的最大公约数 gcd。
3. 判断 c 是否是 gcd 的倍数，若不是则输出 0，结束程序。
4. 初始化解的个数 count 为 0。
5. 使用循环遍历 x 的取值范围 [0, c/a]，对于每个 x，计算 y 的取值为 (c - a * x) / b。 判断 y 是否为非负整数，若是则 count 加一。
6. 输出 count，即为不定方程的非负整数解组数。

代码实现

#include <iostream>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    // 计算最大公约数
    int gcd = 0;
    for (int i = 1; i <= a && i <= b; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }

    // 判断c是否是gcd的倍数
    if (c % gcd != 0) {
        cout << 0 << endl;
        return 0;
    }

    // 遍历x的取值范围，计算y的取值并判断是否满足方程
    int count = 0;
    for (int x = 0; x <= c / a; x++) {
        int y = (c - a * x) / b;
        if (y >= 0 && a * x + b * y == c) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

总结

本篇文章详细讲解了不定方程求解的思路和代码实现，并提供了 C++ 代码示例，帮助您快速理解和解决此类问题。