หาผลคูณของตัวประกอบทั้งหมดของจำนวน N ใน C++

งานคือหาตัวประกอบ (factors) ทั้งหมดของจำนวน N แล้วนำมาคูณกัน พร้อม modulo 1,000,000,000 (1e9) เพื่อป้องกัน overflow

ตัวประกอบของ N คือ จำนวนที่หาร N ลงตัว รวม 1 และ N เอง

ตัวอย่าง

N = 18

ตัวประกอบ: 1, 2, 3, 6, 9, 18

ผลคูณ: 1 × 2 × 3 × 6 × 9 × 18 = 5832

N = 9

ตัวประกอบ: 1, 3, 9

ผลคูณ: 1 × 3 × 9 = 27

แนวทางแก้ปัญหา

1. วน i จาก 1 ถึง √N
2. ถ้า N % i == 0 แสดงว่า i และ N/i เป็นคู่ตัวประกอบ
3. ถ้า i == N/i (รากที่สองพอดี) คูณแค่ครั้งเดียว
4. มิฉะนั้น คูณทั้งคู่ i และ N/i
5. Mod ทุกขั้นตอนด้วย 1e9

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

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

const long long MOD = 1000000000LL;

long long productOfFactors(int N) {
    long long product = 1;
    for (int i = 1; i * 1LL * i <= N; i++) {
        if (N % i == 0) {
            int j = N / i;
            if (i == j) {
                product = (product * i) % MOD;
            } else {
                product = (product * i) % MOD;
                product = (product * j) % MOD;
            }
        }
    }
    return product;
}

int main() {
    int n = 9;
    cout << "Product of factors of " << n << ": " << productOfFactors(n) << endl;
    
    n = 18;
    cout << "Product of factors of " << n << ": " << productOfFactors(n) << endl;
    
    n = 36;
    cout << "Product of factors of " << n << ": " << productOfFactors(n) << endl;
    return 0;
}

ผลลัพธ์

Product of factors of 9: 27
Product of factors of 18: 5832
Product of factors of 36: 10077696

สูตรทางคณิตศาสตร์ (Mathematical Formula)

ถ้า N มีตัวประกอบทั้งหมด d ตัว ผลคูณของตัวประกอบทั้งหมด = N^(d/2)

เหตุผล: ตัวประกอบจับคู่เป็น (f, N/f) ผลคูณแต่ละคู่ = N มี d/2 คู่

ตัวอย่าง N = 18

ตัวประกอบ: 1, 2, 3, 6, 9, 18 (d=6 ตัว)

คู่: (1,18), (2,9), (3,6) → แต่ละคู่คูณได้ 18

ผลคูณ = 18³ = 5832 ✓

ตัวอย่าง N = 36 (Perfect square)

ตัวประกอบ: 1, 2, 3, 4, 6, 9, 12, 18, 36 (d=9 ตัว)

คู่: (1,36), (2,18), (3,12), (4,9) และ (6,6) ตัวกลาง

ผลคูณ = 36⁴ × 6 = 36^(9/2) = 36^4.5 = 10077696 ✓

โค้ดใช้สูตร (เร็วกว่า)

long long productOfFactorsFast(int N) {
    // นับจำนวนตัวประกอบ d
    int d = 0;
    for (int i = 1; i * 1LL * i <= N; i++) {
        if (N % i == 0) {
            d += (i == N / i) ? 1 : 2;
        }
    }
    // คำนวณ N^(d/2) mod MOD
    long long result = 1;
    long long base = N % MOD;
    long long exp = d / 2;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    // ถ้า d คี่ (N เป็น perfect square) คูณเพิ่ม sqrt(N)
    if (d % 2 == 1) {
        int sqrtN = sqrt(N);
        result = (result * sqrtN) % MOD;
    }
    return result;
}

ความซับซ้อน

• วิธีวนลูป: O(√N)
• วิธีสูตร: O(√N) สำหรับนับ d + O(log d) สำหรับ fast exponentiation
• พื้นที่: O(1)