P1218 练36.2 不定方程求解
大约 1 分钟
P1218 练36.2 不定方程求解
【算法】 枚举
【C++】 循环、取模
【难度】 入门
一、题目简述
给定正整数 (均不大于 1000),求不定方程 的非负整数解组数()。
二、解题思路
枚举 从 0 到 (因为 ),对于每个 :
- 计算
- 如果 能被 整除(即 ),设
- 若 (自动满足,因为 ),则找到一组解
手动模拟 :
- x=0: remain=18, 18%3=0, y=6 ✅
- x=1: remain=16, 16%3≠0 ❌
- x=2: remain=14, 14%3≠0 ❌
- x=3: remain=12, 12%3=0, y=4 ✅
- x=4: remain=10, 10%3≠0 ❌
- x=5: remain=8, 8%3≠0 ❌
- x=6: remain=6, 6%3=0, y=2 ✅
- x=7: remain=4, 4%3≠0 ❌
- x=8: remain=2, 2%3≠0 ❌
- x=9: remain=0, 0%3=0, y=0 ✅
- 共 4 组解
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
int cnt = 0;
for (int x = 0; x <= c / a; x++) {
int remain = c - a * x;
if (remain % b == 0) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}四、复杂度分析
- 时间:,最坏 时约 1000 次循环,瞬间完成。
- 空间:。
