โจทย์ข้อนี้เป็นแนว Math ซึ่งสามารถทำได้ $2$ วิธี

วิธีที่ 1 Brute Force

เริ่มจากการสังเกตว่าตัวเลขที่นำมาตรวจสอบนั้นค่าสูงสุดคือ $10^{8}$ จะเห็นว่าค่ามากที่สุดที่สามารถทำให้ $k > 1$ คือ $10^{4}$ โดยค่าที่มากกว่า $10^{4}$ เมื่อยกกำลัง $2$ แล้วจะมากกว่า $10^{8}$ เสมอ

ดังนั้นเราจะหาจำนวนเต็มบวก $a, b$ ที่ทำให้ $a^{b} = y$ โดยตรวจสอบคู่ (a, b) ทั้งหมดที่เป็นไปได้ เริ่มตั้งแต่ $a = 2, 3, 4, \dots, 10^{4}$ และ $b = 2, 3, \dots$ เมื่อถึงค่า $b$ ที่ทำให้ $a^{b}$ มากกว่า $y$ จะไม่พิจารณาค่า $b$ ที่มากกว่านั้น แล้วพิจารณาค่า $a$ ถัดไป

คำตอบคือค่า $b$ ค่าแรก (ถ้าเราไล่ค่า $a$ จากน้อยไปมาก) ที่ทำให้ $a^{b} = y$ ที่เรารู้ว่าคำตอบคือค่าแรก ตัวอย่างเช่น $y = 1\,048\,576$ ซึ่งมีคำตอบที่เป็นไปได้ได้แก่ $2^{20}, 4^{10}, 16^{5}, 32^{4}, 1024^{2}$ สังเกตว่ายิ่งฐานเลขยกกำลังมาก เลขชี้กำลังจะน้อยลง ดังนั้นการไล่ค่า $a$ จากน้อยไปมาก จะทำให้เราได้คำตอบ $b = 20$ ซึ่งมีค่ามากที่สุดเสมอ

วิธีสามารถทำได้เนื่องจากถ้าเราพิจารณา $n\sqrt{y_{max}} = 10^{3}\sqrt{10^{8}} = 10^{7}$ ซึ่งทันใน 1 วินาที

วิธีที่ 2 Number Theory

เนื่องจากจำนวนเต็มบวก $N$ ใดๆ สามารถเขียนในรูปผลคูณของจำนวนเฉพาะได้เสมอหรือก็คือ

$N = p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}} \dots$

โดย $a_{i}$ คือจำนวนเต็มที่ไม่ติดลบและ $p_{i}$ เป็นจำนวนเฉพาะที่ไม่ซ้ำกัน

สังเกตว่าถ้าเราเลือกจำนวนเฉพาะที่มากกว่า $10^{4}$ สองตัวใดๆคูณกันจะมากกว่า $10^{8}$ เสมอดังนั้นตัวเลขที่โจทย์ถามนั้นจะมี $3$ แบบ

1. เป็นจำนวนเฉพาะ
2. เป็นจำนวนประกอบที่มีตัวประกอบเฉพาะที่มากกว่า $10^4$ เพียงตัวเดียว
3. เป็นจำนวนประกอบที่มีตัวประกอบเฉพาะทั้งหมดน้อยกว่าหรือเท่ากับ $10^{4}$

ซึ่งแบบที่ $1$ และ $2$ จะไม่สามารถจัดให้อยู่ในรูป $a^{b}$ ที่ $b > 1$ ได้ ดังนั้นเราจะหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ $10^{4}$ โดยใช้ Sieve of Eratosthenes แล้วแยกตัวประกอบ $y$ ให้อยู่ในรูปของ

$y = 2^{a_{1}}3^{a_{2}}5^{a_{3}} \dots 9973^{a_{1229}}R$

ถ้าเราแยกตัวประกอบให้อยู่ในรูปข้างต้นแล้ว $R$ ไม่เท่ากับ $1$ แปลว่าตัวเลขนี้มีจำนวนเฉพาะที่มากกว่า $10^{4}$ เป็นตัวประกอบ แล้วคำตอบของคำถามก็คือ $GCD(a_{1}, a_{2}, a_{3}, \dots, a_{1229})$ ถ้าเท่ากับ $1$ ก็หมายความว่าตัวเลขนั้นไม่สามารถจัดให้อยู่ในรูป $a^{b}$ ที่ $b > 1$ ได้เช่นกัน

ที่เราบอกว่าคำตอบคือ GCD ตัวอย่างเช่น $y = 3600$ เราจะสามารถแยกตัวประกอบได้เป็น $3600 = 2^{4} \times 3^2 \times 5^{2} = (2^{2} \times 3 \times 5)^{2}$ จะเห็นว่า $a = 2^{2} \times 3 \times 5, b = 2$ ซึ่งเราไม่สามารถจัดรูปให้ $b$ มีค่ามากกว่านี้ได้แล้ว โดยสังเกตว่า $b = 2 = GCD(4, 2, 2)$

ในขั้นตอนการหา GCD นั้นอาจเขียน Euclidean Algorithm หรือใช้ Built-in Function อย่าง __gcd (ใน C++) ก็ได้

Solution Code 1

#include <bits/stdc++.h>

using namespace std;
const int bound = 10000;

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    long long y;
    bool found = false;
    scanf("%lld", &y);
    for (int i = 2; i <= bound; i++) {
      long long now = i * i, power = i;
      for (int j = 2; j <= 32; j++) {
        if (now == y) {
          printf("%d\n", j);
          found = true;
          break;
        }
        now *= power;
      }
      if (found) {
        break;
      }
    }
    if (!found) {
      printf("NO\n");
    }
  }
}

Time Complexity $\mathcal{O}(n\sqrt{y_{max}})$

Solution Code 2

#include <bits/stdc++.h>

using namespace std;
const int MXN = 1e4 + 1;

vector<bool> notprime(MXN, false);
vector<int> prime;

void sieve() {
  for (int i = 2; i < MXN; i++) {
    if (notprime[i]) {
      continue;
    }
    prime.emplace_back(i);
    for (int j = i * 2; j < MXN; j += i) {
      notprime[j] = 1;
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  sieve();
  while (n--) {
    int y, ans = -1;
    scanf("%d", &y);
    for (auto i : prime) {
      if (y % i == 0) {
        int now = 0;
        while (y % i == 0) {
          now++;
          y /= i;
        }
        if (ans == -1) {
          ans = now;
        } else {
          ans = __gcd(ans, now);
        }
      }
    }
    if (y != 1 || ans == 1) {
      printf("NO\n");
    } else {
      printf("%d\n", ans);
    }
  }
}

Time Complexity $\mathcal{O}(n\log{}(y_{max}) + \sqrt{y_{max}}\log{}(\sqrt{y_{max}}))$