题目要求计算不定方程非负整数解的个数。
总时间限制: 1000ms 内存限制: 65536kB
给定正整数a,b,c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。
一行,包含三个正整数a,b,c,两个整数之间用单个空格隔开。每个数均不大于1000。
一个整数,即不定方程的非负整数解组数。
2 3 18
4
由于解均为非负整数,所以在穷举x,y的时候从0开始,到c/a,和c/b,即x最大时,y为0,反之亦然。
#include <iostream>
using namespace std;
int main() {
int a, b, c, i, j, sum = 0;
cin >> a >> b >> c;
for (i = 0; i <= c / a + 1; ++i) {
for (j = 0; j <= c / b + 1; ++j) {
if (a * i + b * j == c) {
sum++;
}
}
}
cout << sum << endl;
return 0;
}
4139.cpp 代码长度:264B 内存:200kB 时间:13ms 通过率:99% 最小内存:200kB 最短时间:0ms
这里主要考察x,y的上限,两重循环来穷举满足的方程个数即可。
有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。