ตรวจสอบตัวเลขใหญ่หาร 13 ลงตัวใน C++

ปัญหา

ตรวจสอบตัวเลขขนาดใหญ่ (เกิน range ของ long long) ว่าหาร 13 ลงตัวหรือไม่ โดยรับ input เป็น string

กฎการหาร 13

มี 2 วิธีหลัก:

วิธีที่ 1: Alternating Sum of 3-digit Blocks

แบ่งตัวเลขเป็นกลุ่มละ 3 หลักจากขวาไปซ้าย แล้วบวก-ลบสลับกัน

ตัวอย่าง: 2911285 → กลุ่ม: 2 | 911 | 285

Alternating sum: 2 - 911 + 285 = -624

-624 ÷ 13 = -48 → หารลงตัว ✓

วิธีที่ 2: Recursive Rule (Last digit × 4)

ตัดหลักสุดท้าย คูณ 4 บวกกับส่วนที่เหลือ ทำซ้ำจนเหลือเลขเล็ก

ตัวอย่าง: 2353

• 235 + 3×4 = 247
• 24 + 7×4 = 52
• 52 ÷ 13 = 4 → หารลงตัว ✓

ตัวอย่างโค้ด C++ (วิธีที่ 1: 3-digit blocks)

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

bool isDivisibleBy13(string num) {
    int len = num.length();
    
    // Pad leading zeros ทำให้ความยาวหาร 3 ลงตัว
    if (len % 3 == 1) num = "00" + num;
    else if (len % 3 == 2) num = "0" + num;
    
    int sum = 0;
    int sign = 1;
    
    // ประมวลผลจากขวาไปซ้าย กลุ่มละ 3 หลัก
    for (int i = num.length() - 1; i >= 0; i -= 3) {
        int block = (num[i-2] - '0') * 100 
                  + (num[i-1] - '0') * 10 
                  + (num[i] - '0');
        sum += sign * block;
        sign *= -1;
    }
    
    return abs(sum) % 13 == 0;
}

int main() {
    string num = "83959092724";
    if (isDivisibleBy13(num))
        cout << "Divisible by 13" << endl;
    else
        cout << "Not divisible by 13" << endl;
    
    // ทดสอบเพิ่ม
    cout << "2911285: " << (isDivisibleBy13("2911285") ? "Yes" : "No") << endl;
    cout << "123456: " << (isDivisibleBy13("123456") ? "Yes" : "No") << endl;
    
    return 0;
}

ผลลัพธ์

Divisible by 13
2911285: Yes
123456: No

ตัวอย่างโค้ด C++ (วิธีที่ 2: Recursive ×4)

bool isDiv13Recursive(string num) {
    while (num.length() > 2) { // ทำจนเหลือ 2 หลัก
        int last = num.back() - '0';
        num.pop_back();
        
        // บวก last*4 เข้ากับตัวเลขที่เหลือ
        int carry = last * 4;
        for (int i = num.length() - 1; i >= 0 && carry > 0; i--) {
            int digit = num[i] - '0' + carry;
            num[i] = '0' + (digit % 10);
            carry = digit / 10;
        }
        if (carry > 0) num = to_string(carry) + num;
    }
    int val = stoi(num);
    return val % 13 == 0;
}

เปรียบเทียบ