การตรวจสอบว่าเลข N เป็นกำลังของเลข a ใน C++

กำลังของเลข (Power) หมายถึง การคูณเลขตัวเดียวกันซ้ำๆ เช่น a ยกกำลัง b = a × a × ... × a (b ครั้ง)

คุณสมบัติพื้นฐานของกำลัง

• เลขใด ยกกำลัง 0 = 1
• เลขใด ยกกำลัง 1 = ตัวมันเอง
• เลขยกกำลังลบ = 1 หาร ด้วยเลขยกกำลังบวก เช่น a⁻³ = 1/a³

ปัญหา

ได้รับจำนวน N และ a ต้องตรวจสอบว่า N เป็นกำลังของ a หรือไม่ (คือ N = aᵏ สำหรับ k เป็นจำนวนเต็มบวก)

ตัวอย่าง

Input − N = 64, a = 2

Output − Yes (เพราะ 64 = 2⁶)

วิธีแก้

หาร N ด้วย a ซ้ำๆ จนกว่าจะไม่ลงตัว หากสุดท้ายเหลือ 1 → เป็นกำลังของ a

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

bool isAPowerNumber(int x, long int y) {
    if (x == 1) return (y == 1);
    long int power = 1;
    while (power < y)
        power *= x;
    return (power == y);
}

int main() {
    int N = 625, a = 5;
    if (isAPowerNumber(a, N))
        cout << N << " is a power of " << a;
    else
        cout << N << " is not power of " << a;
    return 0;
}

ผลลัพธ์

625 is a power of 5

หมายเหตุ

วิธีนี้ทำงานได้ดีกับจำนวนที่ไม่ใหญ่เกินไป สำหรับจำนวนใหญ่ควรใช้ลอการิทึมหรือ bit manipulation