Giả sử chúng ta có một số nguyên N. Nhiệm vụ là tìm tất cả các thừa số của N và hiển thị tích của bốn thừa số của N, sao cho -
-
Tổng bốn yếu tố của chúng bằng N
-
Tích của bốn yếu tố là tối đa
Giả sử số là 24, thì tích là 1296. Như chúng ta biết tất cả các thừa số là 1, 2, 3, 4, 6, 8, 12, 24. Ta phải chọn thừa số 6 bốn lần. Vậy 6 + 6 + 6 + 6 =24. Ở đây tích là cực đại.
Để giải quyết điều này, chúng ta phải tìm tất cả các hệ số từ 1 đến N, sau đó chúng ta phải kiểm tra các điều kiện này
-
Nếu N là số nguyên tố thì câu trả lời sẽ là sai
-
Nếu n đã cho chia hết cho 4 thì đáp số sẽ là x ^ 4. Trong đó x là thương khi n chia hết cho 4.
-
Khi đó nếu có thể tìm được đáp án thì đáp án đó phải bao gồm thừa số cuối thứ ba hai lần. Sau đó, chạy vòng lặp lồng nhau cho hai yếu tố còn lại.
Ví dụ
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool isPrime(int n) {
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
void get_factors(int N, vector<int> fact_vectors[]) {
for (int i = 2; i < N; i++) {
for (int j = 1; j * j <= i; j++) {
if (i % j == 0) {
if (i / j == j)
fact_vectors[i].push_back(j);
else {
fact_vectors[i].push_back(j);
fact_vectors[i].push_back(i / j);
}
}
}
sort(fact_vectors[i].begin(), fact_vectors[i].end());
}
}
int getProduct(int n) {
vector<int> v[n + 100];
get_factors(n + 100, v);
if (n % 4 == 0) {
int x = n / 4;
x *= x;
return x * x;
} else {
if (isPrime[n])
return -1;
else {
int ans = -1;
if (v[n].size() > 2) {
int fac = v[n][v[n].size() - 3];
for (int i = v[n].size() - 1; i >= 0; i--) {
for (int j = v[n].size() - 1; j >= 0; j--) {
if ((fac * 2) + (v[n][j] + v[n][i]) == n)
ans = max(ans, fac * fac * v[n][j] * v[n][i]);
}
}
return ans;
}
}
}
}
int main() {
int n = 24;
cout << "The product is: " << getProduct(n);
} Đầu ra
The product is: 1296