Thuật toán vét cạn (Brute Force): khi nào đủ qua test, mẹo khử vòng lặp và code C++, Python

#include <iostream>
using namespace std;

// Cách 1: Vét cạn ngây thơ 3 vòng lặp lồng nhau O(N^3)
long long dem_bo_ba_3_vong(int n, int s) {
    long long dem = 0;
    for (int a = 0; a <= n; ++a) {
        for (int b = 0; b <= n; ++b) {
            for (int c = 0; c <= n; ++c) {
                if (a + b + c == s) {
                    ++dem;
                }
            }
        }
    }
    return dem;
}

// Cách 2: Khử vòng lặp c bằng biến đổi đại số c = s - a - b -> giảm còn O(N^2)
long long dem_bo_ba_2_vong(int n, int s) {
    long long dem = 0;
    for (int a = 0; a <= n; ++a) {
        for (int b = 0; b <= n; ++b) {
            int c = s - a - b;
            if (0 <= c && c <= n) {
                ++dem;
            }
        }
    }
    return dem;
}

int main() {
    // Test 1: N = 2, S = 2 -> 6 bộ: (0,0,2), (0,1,1), (0,2,0), (1,0,1), (1,1,0), (2,0,0)
    cout << "N=2, S=2 -> 3vong: " << dem_bo_ba_3_vong(2, 2)
         << " | 2vong: " << dem_bo_ba_2_vong(2, 2) << "\n";

    // Test 2: N = 10, S = 15 -> 91 bộ
    cout << "N=10, S=15 -> 3vong: " << dem_bo_ba_3_vong(10, 15)
         << " | 2vong: " << dem_bo_ba_2_vong(10, 15) << "\n";

    // Test 3: N = 50, S = 75 -> 1951 bộ
    cout << "N=50, S=75 -> 3vong: " << dem_bo_ba_3_vong(50, 75)
         << " | 2vong: " << dem_bo_ba_2_vong(50, 75) << "\n";

    return 0;
}

def dem_bo_ba_3_vong(n: int, s: int) -> int:
    """Cách 1: Vét cạn ngây thơ 3 vòng lặp lồng nhau O(N^3)."""
    dem = 0
    for a in range(n + 1):
        for b in range(n + 1):
            for c in range(n + 1):
                if a + b + c == s:
                    dem += 1
    return dem


def dem_bo_ba_2_vong(n: int, s: int) -> int:
    """Cách 2: Khử vòng lặp c bằng biến đổi đại số c = s - a - b -> O(N^2)."""
    dem = 0
    for a in range(n + 1):
        for b in range(n + 1):
            c = s - a - b
            if 0 <= c <= n:
                dem += 1
    return dem


if __name__ == "__main__":
    # Test 1: N = 2, S = 2 -> 6 bộ
    print(f"N=2, S=2 -> 3vong: {dem_bo_ba_3_vong(2, 2)} | 2vong: {dem_bo_ba_2_vong(2, 2)}")

    # Test 2: N = 10, S = 15 -> 91 bộ
    print(f"N=10, S=15 -> 3vong: {dem_bo_ba_3_vong(10, 15)} | 2vong: {dem_bo_ba_2_vong(10, 15)}")

    # Test 3: N = 50, S = 75 -> 1951 bộ
    print(f"N=50, S=75 -> 3vong: {dem_bo_ba_3_vong(50, 75)} | 2vong: {dem_bo_ba_2_vong(50, 75)}")

#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Tìm mọi cặp nguyên dương (x, y) với 1 <= x <= y sao cho x^2 + y^2 = n
// Thu hẹp miền duyệt: vì x <= y nên 2 * x^2 <= n -> chỉ tốn O(sqrt(n)) bước
vector<pair<long long, long long>> tim_cap_binh_phuong(long long n) {
    vector<pair<long long, long long>> ket_qua;
    for (long long x = 1; 2 * x * x <= n; ++x) {
        long long phan_con = n - x * x;
        long long y = (long long)round(sqrt((double)phan_con));
        if (y >= x && y * y == phan_con) {
            ket_qua.push_back({x, y});
        }
    }
    return ket_qua;
}

void in_nghiem(long long n) {
    auto ds = tim_cap_binh_phuong(n);
    cout << "N=" << n << ": ";
    if (ds.empty()) {
        cout << "NONE\n";
        return;
    }
    for (size_t i = 0; i < ds.size(); ++i) {
        cout << "(" << ds[i].first << "," << ds[i].second << ")"
             << (i + 1 == ds.size() ? "\n" : " ");
    }
}

int main() {
    in_nghiem(25); // N=25: (3,4)
    in_nghiem(50); // N=50: (1,7) (5,5)
    in_nghiem(65); // N=65: (1,8) (4,7)
    in_nghiem(7);  // N=7: NONE
    return 0;
}

import math


def tim_cap_binh_phuong(n: int) -> list[tuple[int, int]]:
    """Tìm mọi cặp nguyên dương (x, y) với 1 <= x <= y sao cho x^2 + y^2 = n trong O(sqrt(n))."""
    ket_qua: list[tuple[int, int]] = []
    x = 1
    while 2 * x * x <= n:
        phan_con = n - x * x
        y = math.isqrt(phan_con)
        if y >= x and y * y == phan_con:
            ket_qua.append((x, y))
        x += 1
    return ket_qua


def in_nghiem(n: int) -> None:
    ds = tim_cap_binh_phuong(n)
    if not ds:
        print(f"N={n}: NONE")
    else:
        chuoi = " ".join(f"({x},{y})" for x, y in ds)
        print(f"N={n}: {chuoi}")


if __name__ == "__main__":
    in_nghiem(25)  # N=25: (3,4)
    in_nghiem(50)  # N=50: (1,7) (5,5)
    in_nghiem(65)  # N=65: (1,8) (4,7)
    in_nghiem(7)   # N=7: NONE