แนวคิด
สำหรับหมายเลข n ที่กำหนด ภารกิจคือตรวจสอบว่า n เป็นหมายเลขโทรจันหรือไม่ หมายเลขโทรจันถูกกำหนดให้เป็นตัวเลขที่เป็นตัวเลขที่แข็งแกร่งโดยไม่มีพลังที่สมบูรณ์แบบ เราสามารถพูดได้ว่าจำนวน n ถือเป็นจำนวนที่หนักแน่น ถ้าสำหรับทุกตัวหารเฉพาะหรือตัวประกอบ p ของ n, p^2 เป็นตัวหารด้วย เราสามารถพูดอีกอย่างหนึ่งได้ว่า ตัวประกอบเฉพาะทุกตัวปรากฏขึ้นอย่างน้อยสองครั้ง เราควรจำไว้ว่าหมายเลขโทรจันทั้งหมดนั้นแข็งแกร่ง แต่ในทางกลับกัน นั่นไม่ใช่ตัวเลขที่แข็งแกร่งทั้งหมดที่เป็นตัวเลขโทรจัน:เฉพาะตัวเลขที่ไม่สามารถแสดงเป็น a^b โดยที่ a และ b เป็นจำนวนเต็มบวกที่มากกว่า 1
ป้อนข้อมูล
n = 72 72 is expressed as 6×6×2 i.e. (6^2)×2 i.e. Strong Number but without perfect power.
ผลผลิต
YES
ป้อนข้อมูล
n = 16 16 is expressed as 2×2×2×2 i.e. 2^4 i.e. Strong number with perfect power.
ผลผลิต
NO
แนวทาง
ขั้นแรก เราต้องเก็บการนับของปัจจัยเฉพาะแต่ละตัวและตรวจสอบว่าการนับนั้นมากกว่า 2 จะเป็นตัวเลขที่แข็งแกร่งหรือไม่
ในกรณีของขั้นตอนต่อไป เราต้องตรวจสอบว่าตัวเลขที่กำหนดนั้นแสดงเป็น a^b หรือไม่ ถ้ามันไม่ได้แสดงเป็น a^b เราสามารถพูดได้ว่ามันเป็นพลังที่สมบูรณ์แบบ มิฉะนั้นจะเป็นพลังที่สมบูรณ์แบบ สุดท้าย ในขั้นตอนสุดท้าย เราสามารถสรุปได้ว่าหากตัวเลขที่ให้มานี้แรงแต่ไม่มีกำลังสมบูรณ์ ตัวเลขดังกล่าวจะถือเป็นหมายเลขโทรจัน
ตัวอย่าง
// 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;
} ผลลัพธ์
YES
