C++에서 주어진 방정식을 만족하는 n개의 양의 정수 찾기

이 문제에서 우리는 세 개의 값 A, B, N을 받습니다. 우리의 임무는 주어진 방정식을 만족하는 n개의 양의 정수를 찾는 것입니다.

문제 설명 − 두 방정식을 모두 만족하는 N개의 양수 값을 찾아야 합니다.

x12 + x22 + … xn2 ≥ A
x1 + x2 + … xn ≤ B

존재하는 경우 n개의 값을 인쇄하고, 그렇지 않으면 -1을 인쇄합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

N = 4, A = 65, B = 16

출력

1 1 1 8

설명

방정식은 -

12 + 12 + 12 + 82 = 1 + 1 + 1 + 64 = 67 ≥ 65
1 + 1 + 1 + 8 = 11 < 16

해결 방법

문제에 대한 간단한 해결책은 제곱합을 최대화하는 것입니다. 아이디어는 하나의 숫자를 기본 숫자로 사용하여 제곱합을 최대화하고 다른 숫자를 1로 사용하는 것입니다. 따라서 이를 사용하여 제곱합을 최대화하고 합 조건을 만족할 수 있습니다.

우리 솔루션의 작동을 설명하는 프로그램

예

#include <bits/stdc++.h>
using namespace std;
void findNintegers(int N, int A, int B) {
   vector<int> 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 i = 0; i < N; i++)
      vals += numbers[i] * numbers[i];
   if (vals < A) {
      cout << "-1";
      return;
   }
   for (int i = 0; i < N; i++)
      cout << numbers[i] << " ";
}
int main(){
   int N = 4, A = 65, B = 17;
   cout<<N<<" positive integers that satisfy the given equations are ";
   findNintegers(N, A, B);
   return 0;
}

출력

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