หา GCD สูงสุดของ N จำนวนเต็มที่มีผลคูณกำหนด ใน C++

บทนำ

กำหนดจำนวนเต็มสองจำนวน N และ P โดย P เป็นผลคูณของ N จำนวนเต็มที่ไม่ทราบค่า ต้องการหา GCD สูงสุดที่เป็นไปได้ของ N จำนวนนั้น

ตัวอย่าง: N = 3, P = 24 → กลุ่มที่เป็นไปได้: {1,1,24}, {1,2,12}, {1,3,8}, {1,4,6}, {2,2,6}, {2,3,4} → GCD ตามลำดับ: 1,1,1,1,2,1 → คำตอบ = 2

หลักการคำนวณ

แยกตัวประกอบเฉพาะ (prime factorization) ของ P แล้วเก็บใน hashmap หาก P = p₁^k₁ × p₂^k₂ × ... × pₙ^kₙ

GCD สูงสุด = p₁^(k₁/N) × p₂^(k₂/N) × ... × pₙ^(kₙ/N) (ใช้การหารจำนวนเต็ม)

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

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

long getMaxGCD(long N, long p) {
    int gcd = 1;
    unordered_map<int, int> prime_factors;
    
    for (int i = 2; i * i <= p; i++) {
        while (p % i == 0) {
            prime_factors[i]++;
            p /= i;
        }
    }
    if (p != 1)
        prime_factors[p]++;
    
    for (auto v : prime_factors)
        gcd = gcd * pow(v.first, v.second / N);
    
    return gcd;
}

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

ผลลัพธ์

MAX GCD: 2