【GESP】C++二级练习 luogu-B2086, 不定方程求解

GESP二级练习，多层循环练习，难度★✮☆☆☆。

luogu-B2086

题目要求

题目描述

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

输入格式

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

输出格式

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

样例输入 #1

2 3 18

样例输出 #1

4

---

题目分析

两种解题思路总结：

1. 第一种解题思路是使用两层循环，分别遍历 $x$ 和 $y$ 的所有可能取值，然后判断是否满足方程条件，如果满足则计数器加1。这种解题思路的时间复杂度为 $O(n^2)$，其中 $n$ 为 $x$ 和 $y$ 的最大取值。

2. 第二种解题思路是只使用一层循环，遍历 $x$ 的所有可能取值，然后判断是否满足方程条件，如果满足则计数器加1。这种解题思路的时间复杂度为 $O(n)$，其中 $n$ 为 $x$ 的最大取值。

示例代码

思路一

#include <iostream>
using namespace std;
int main() {
    int a, b, c; // 定义三个整数变量a, b, c
    cin >> a >> b >> c; // 从输入流中读取a, b, c的值
    int count = 0; // 初始化计数器为0
    for (int i = 0; i <= 1000; i++) { // 外层循环，遍历i从0到1000
        for (int j = 0; j <= 1000; j++) { // 内层循环，遍历j从0到1000
            if (a * i + b * j == c) { // 判断是否满足方程条件
                count++; // 如果满足，则计数器加1
            }
        }
    }
    cout << count; // 输出计数器的值，即解的个数
    return 0;
}

思路二

#include <iostream>
using namespace std;
int main() {
    int a, b, c; // 定义三个整数变量a, b, c
    cin >> a >> b >> c; // 从输入流中读取a, b, c的值
    int count = 0; // 初始化计数器为0
    for (int i = 0; i <= 1000; i++) { // 外层循环，遍历i从0到1000
        if ((c - a * i) >= 0 && (c - a * i) % b == 0) { // 判断是否满足方程条件
            count++; // 如果满足，则计数器加1
        }
    }
    cout << count; // 输出计数器的值，即解的个数
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。