หา GCD สูงสุดจากผลคูณของจำนวนที่ไม่ทราบค่า ใน C++

บทนำ

โจทย์เดียวกับ ID 1004081890 แต่ใช้วิธีการแยกตัวประกอบเฉพาะแบบไม่ใช้ hashmap

กำหนด N และ P (ผลคูณของ N จำนวน) หา GCD สูงสุดที่เป็นไปได้

ตัวอย่าง

N=3, P=24 → กลุ่มที่เป็นไปได้: {1,1,24}, {1,2,12}, {1,3,8}, {1,4,6}, {2,2,6}, {2,3,4} → GCD สูงสุด = 2

แนวคิด

แยกตัวประกอบเฉพาะของ P แล้วแต่ละตัวประกอบ เลขยกกำลังหารด้วย N (ปัดลง) นำมาคูณกัน

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

#include <iostream>
#include <cmath>
using namespace std;

long getMaxGCD(long n, long p) {
    int count = 0;
    long gcd = 1;
    
    // ตัวประกอบ 2
    while (p % 2 == 0) {
        p >>= 1;
        count++;
    }
    if (count > 0)
        gcd = gcd * (long)pow(2, count / n);
    
    // ตัวประกอบคี่
    for (long i = 3; i <= sqrt(p); i += 2) {
        count = 0;
        while (p % i == 0) {
            count++;
            p /= i;
        }
        if (count > 0)
            gcd = gcd * (long)pow(i, count / n);
    }
    
    // ถ้า p ที่เหลือเป็นเฉพาะ
    if (p > 2)
        gcd = gcd * (long)pow(p, 1 / n);
    
    return gcd;
}

int main() {
    long n = 3, p = 24;
    cout << "MAX GCD: " << getMaxGCD(n, p);
    return 0;
}

ผลลัพธ์

MAX GCD: 2