Khái niệm
Đối với số n đã cho, nhiệm vụ là xác minh xem n có phải là Số Trojan hay không. Số Trojan được định nghĩa là một con số là một con số mạnh mẽ mà không có một sức mạnh hoàn hảo. Chúng ta có thể nói rằng một số n được coi là một số mạnh nếu, với mọi ước nguyên tố hoặc thừa số p của n, p ^ 2 cũng là một ước số. Có thể nói theo một cách khác, mọi thừa số nguyên tố đều xuất hiện ít nhất hai lần. Chúng ta nên nhớ rằng tất cả các số Trojan đều rất mạnh. Nhưng điều đó không đúng khi ngược lại, điều đó có nghĩa là không phải tất cả các số mạnh đều là số Trojan:chỉ những số không thể được biểu diễn dưới dạng a ^ b, trong đó a và b là các số nguyên dương lớn hơn 1.
Đầu vào
n = 72 72 is expressed as 6×6×2 i.e. (6^2)×2 i.e. Strong Number but without perfect power.
Đầu ra
YES
Đầu vào
n = 16 16 is expressed as 2×2×2×2 i.e. 2^4 i.e. Strong number with perfect power.
Đầu ra
NO
Phương pháp tiếp cận
Lúc đầu, chúng ta phải lưu trữ số đếm của mỗi thừa số nguyên tố và xác minh nếu số lượng lớn hơn 2 thì đó sẽ là Số mạnh.
Trong trường hợp của bước tiếp theo, chúng ta phải xác minh xem số đã cho có được biểu thị dưới dạng a ^ b hay không. Nếu nó không được biểu thị bằng a ^ b, chúng ta có thể nói rằng nó là sức mạnh hoàn hảo; nếu không thì đó là sức mạnh hoàn hảo. Cuối cùng, ở bước cuối cùng, chúng ta có thể kết luận rằng nếu số nhất định này mạnh mà không có sức mạnh hoàn hảo, thì số đó được coi là Số Trojan.
Ví dụ
// CPP program to check if a number is
// Trojan Number or not
#include <bits/stdc++.h>
using namespace std;
bool isPerfectPower1(int n1){
if (n1 == 1)
return true;
for (int x1 = 2; x1 <= sqrt(n1); x1++) {
int y1 = 2;
int p1 = pow(x1, y1);
while (p1 <= n1 && p1 > 0) {
if (p1 == n1)
return true;
y1++;
p1 = pow(x1, y1);
}
}
return false;
}
bool isStrongNumber1(int n1){
unordered_map<int, int> count1;
while (n1 % 2 == 0) {
n1 = n1 / 2;
count1[2]++;
}
for (int i1 = 3; i1 <= sqrt(n1); i1 += 2) {
while (n1 % i1 == 0) {
n1 = n1 / i1;
count1[i1]++;
}
}
if (n1 > 2)
count1[n1]++;
int flag1 = 0;
for (auto b : count1) {
if (b.second == 1) {
flag1 = 1;
break;
}
}
if (flag1 == 1)
return false;
else
return true;
}
bool isTrojan1(int n1){
if (!isPerfectPower1(n1) && isStrongNumber1(n1))
return true;
else
return false;
}
// Driver Code
int main(){
int n1 = 72;
if (isTrojan1(n1))
cout << "YES";
else
cout << "NO";
return 0;
} Đầu ra
Yes