练36.2 不定方程求解

解题思路

枚举x=0～floor(c/a)，余量r=c-ax。若r能被b整除，则唯一得到非负整数y=r/b，计一组。

正确性说明

每组解唯一确定x，枚举覆盖全部可能x；余量可整除时对应且只对应一个合法y，因此不重不漏。

易错点

x和y都允许0，不能从1枚举。

复杂度

时间O(c/a)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    int ans = 0;
    for (int x = 0; x * a <= c; x++)
        if ((c - x * a) % b == 0)
            ans++;
    cout << ans << "\n";
    return 0;
}