ตรวจสอบตัวเลขหารผลรวมแฟกทอเรียลของหลักตัวเองลงตัวใน C++

ปัญหา

ให้ตัวเลข n ตรวจสอบว่า n หาร (ผลรวมของแฟกทอเรียลของแต่ละหลัก) ลงตัวหรือไม่

ตัวอย่าง: n = 19

หลัก: 1, 9 1! + 9! = 1 + 362880 = 362881 362881 ÷ 19 = 19099 → ลงตัว ✓

อัลกอริทึม

1. แยกหลักของ n
2. คำนวณแฟกทอเรียลแต่ละหลัก (0! = 1, 1! = 1, 2! = 2, ..., 9! = 362880)
3. รวมแฟกทอเรียลทั้งหมด
4. ตรวจสอบ sum % n == 0

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

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

// Precompute factorials 0! to 9!
const array<int, 10> FACT = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

bool dividesFactorialDigitSum(int num) {
    if (num == 0) return false; // 0 ไม่มีตัวหาร
    
    int original = num;
    int sum = 0;
    
    while (num > 0) {
        int digit = num % 10;
        sum += FACT[digit];
        num /= 10;
    }
    
    return (sum % original == 0);
}

int main() {
    int testNumbers[] = {19, 1, 2, 3, 10, 11, 12, 145, 40585};
    
    for (int n : testNumbers) {
        if (dividesFactorialDigitSum(n)) {
            // แสดงรายละเอียด
            int temp = n, sum = 0;
            cout << n << ": ";
            while (temp > 0) {
                int d = temp % 10;
                sum += FACT[d];
                cout << d << "!+" ;
                temp /= 10;
            }
            cout << "\b = " << sum << " → " << sum << " % " << n << " = " << (sum % n) << " ✓" << endl;
        } else {
            cout << n << ": does not divide factorial digit sum" << endl;
        }
    }
    return 0;
}

ผลลัพธ์

19: 9!+1! = 362881 → 362881 % 19 = 0 ✓
1: 1! = 1 → 1 % 1 = 0 ✓
2: 2! = 2 → 2 % 2 = 0 ✓
3: 3! = 6 → 6 % 3 = 0 ✓
10: 0!+1! = 2 → 2 % 10 = 2 ✗
11: 1!+1! = 2 → 2 % 11 = 2 ✗
12: 2!+1! = 3 → 3 % 12 = 3 ✗
145: 5!+4!+1! = 145 → 145 % 145 = 0 ✓
40585: 5!+8!+5!+0!+4! = 40585 → 40585 % 40585 = 0 ✓

ข้อสังเกตน่าสนใจ

• 145 และ 40585 เป็น Factorions (เท่ากับผลรวมแฟกทอเรียลหลักตัวเอง)
• Factorions ในฐาน 10 มีเพียง 4 ตัว: 1, 2, 145, 40585
• ตัวเลขที่หารผลรวมแฟกทอเรียลหลักลงตัว มีมากกว่า Factorions

ความซับซ้อน

• เวลา: O(d) โดย d = จำนวนหลัก (สูงสุด 10-19 หลักสำหรับ 64-bit)
• พื้นที่: O(1) - lookup table ขนาด 10