Tìm N số nguyên dương thỏa mãn hệ bất phương trình trong C++

Giới thiệu

Cho A, B, N. Tìm N số nguyên dương x₁...xₙ thỏa mãn:

x₁² + x₂² + ... + xₙ² ≥ A
x₁ + x₂ + ... + xₙ ≤ B

Ví dụ minh họa

Đầu vào

N = 4, A = 65, B = 16

Đầu ra

1 1 1 8

Giải thích

1²+1²+1²+8² = 67 ≥ 65
1+1+1+8 = 11 ≤ 16

Phương pháp giải

Để tối đa hóa tổng bình phương với tổng cố định, tập trung giá trị vào một số, các số còn lại để bằng 1 (giá trị nhỏ nhất). Gán N-1 số đầu = 1, số cuối = B - (N-1). Kiểm tra điều kiện bình phương.

Chương trình minh họa

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

void findNIntegers(int N, int A, int B) {
    vector numbers;
    for (int i = 0; i < N - 1; i++)
        numbers.push_back(1);
    
    if (B - (N - 1) <= 0) {
        cout << "-1";
        return;
    }
    numbers.push_back(B - (N - 1));
    
    int vals = 0;
    for (int x : numbers)
        vals += x * x;
    
    if (vals < A) {
        cout << "-1";
        return;
    }
    for (int x : numbers)
        cout << x << " ";
}

int main() {
    int N = 4, A = 65, B = 17;
    cout << N << " positive integers that satisfy the equations are ";
    findNIntegers(N, A, B);
    return 0;
}

Đầu ra

4 positive integers that satisfy the given equations are 1 1 1 14