C++で与えられた方程式を満たすn個の正の整数を見つけます

この問題では、A、B、Nの3つの値が与えられます。私たちのタスクは、与えられた方程式を満たす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つの数値を主数値として使用して平方和を最大化し、別の数値を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