Cho tập A gồm 16 số nguyên dương đầu tiên. Hãy tìm số nguyên dương k nhỏ nhất có tính chất. Trong mỗi tập con gồm k phẩn tử của A đều tồn tại 2 số phân biệt a,b sao cho \(a^2+b^2 là \) số nguyên tố
@Akai Haruma
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
#include <iostream>
#include <vector>
using namespace std;
vector<int> primeFactors(int n) {
vector<int> factors;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
if (n > 1) factors.push_back(n);
return factors;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> factors = primeFactors(k);
int sum = accumulate(a.begin(), a.end(), 0);
vector<vector<bool>> dp(n+1, vector<bool>(sum+1, false));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= sum; ++j) {
dp[i][j] = dp[i-1][j];
if (j >= a[i-1]) {
for (int factor : factors) {
if (a[i-1] % factor == 0) {
dp[i][j] = dp[i][j] || dp[i-1][j-a[i-1]];
break;
}
}
}
}
}
for (int j = 0; j <= sum; ++j) {
if (dp[n][j]) {
cout << j << endl;
break;
}
}
return 0;
}
Thật lòng xin lỗi vì bây giờ mới nhìn thấy bài tag của bạn.
Lời giải:
Tập hợp $A$ bao gồm $8$ số chẵn và $8$ số lẻ.
Nếu \(k\leq 8\). Ta có thể chọn một tập hợp \(S\) gồm $k$ phần tử chỉ gồm toàn số chẵn hoặc toàn số lẻ. Khi đó, mọi \(a,b\in S\) thì \(\left\{\begin{matrix} a^2+b^2\vdots 2\\ a^2+b^2> 2\end{matrix}\right.\) hay \(a^2+b^2\not\in\mathbb{P}\) (không thỏa mãn)
Do đó \(k>8\)
Nếu \(k=9\). Ta sẽ chỉ ra $k=9$ là số nhỏ nhất thỏa mãn bằng cách xét 8 nhóm sau:
\((1,16)\); \((2,15); (3,10); (4, 11); (5,6); (7,12); (8, 13); (9, 14)\)
(các cặp này được lấy ra từ 16 số nguyên dương thỏa mãn tổng các bình phương là số nguyên tố)
Khi đó trong tập $S$ gồm $9$ phần tử, theo nguyên lý Dirichlet ta luôn tồn tại ít nhất \(\left[\frac{9}{8}\right]+1=2\) phần tử thuộc cùng một nhóm, tức là trong tập S gồm $9$ phần tử luôn chọn ra được 2 phần tử \((a,b)\) thỏa mãn \(a^2+b^2\) là số nguyên tố.
Vậy \(k=9\)
k nhỏ nhất = 9.