Tìm nghiệm nguyên dương cho phương trình cho trước C++

Cho hàm f(x, y) tăng dần theo x và y. Tìm tất cả cặp (x, y) nguyên dương thỏa f(x, y) = z.

Ví dụ

f(x,y) = x + y (id=1), z = 7 → (1,6), (2,5), (3,4), (4,3), (5,2), (6,1)

f(x,y) = x × y (id=2), z = 6 → (1,6), (2,3), (3,2), (6,1)

Thuật toán brute force

Duyệt x từ 1 đến 1000, y từ 1 đến 1000, kiểm tra f(x,y) == z. Vì f tăng dần, có thể break sớm.

Chương trình mẫu

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

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << (j+1 z) {
                    break; // f tăng dần theo y
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    CustomFunction c(1); // f(x,y) = x + y
    print_vector(ob.findSolution(c, 7));
    return 0;
}

Kết quả

[[1, 6], [2, 5], [3, 4], [4, 3], [5, 2], [6, 1]]

Tối ưu hóa: Vì f tăng dần, với mỗi x, binary search y hoặc two-pointer (x tăng, y giảm). Độ phức tạp O(1000) thay vì O(1000²).