บทนำ
การตรวจสอบว่าเลขใหญ่ (เกินชนิดข้อมูลมาตรฐาน) หาร 37 ลงตัวหรือไม่ สามารถทำได้โดยคณิตศาสตร์เฉพาะของ 37
หลักการคณิตศาสตร์
1000 ≡ 1 (mod 37) ดังนั้น จัดกลุ่มเลขทีละ 3 หลัก (จากขวาไปซ้าย) แล้วบวกกัน หากผลรวมหาร 37 ลงตัว ตัวเลขเดิมก็หาร 37 ลงตัว
ขั้นตอนการแก้ปัญหา
- รับตัวเลขเป็นสตริง
- เติม 0 ด้านหน้าให้ความยาวหาร 3 ลงตัว
- แบ่งกลุ่มทีละ 3 หลัก แปลงเป็นตัวเลข บวกกัน
- ถ้าผลรวม ≥ 1000 ให้ทำซ้ำขั้นตอน 2-3 ด้วยผลรวมใหม่
- ตรวจสอบผลรวมสุดท้ายว่าหาร 37 ลงตัวหรือไม่
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
bool isNumberDivisibleBy37(string number, int n) {
if (number == "0") {
return 0;
}
if (n % 3 == 1) {
number = "00" + number;
n += 2;
} else if (n % 3 == 2) {
number = "0" + number;
n += 1;
}
int groups_sum = 0;
while (n != 0) {
string group = number.substr(n - 3, 3);
int group_value = (group[0] - '0') * 100 + (group[1] - '0') * 10 + (group[2] - '0') * 1;
groups_sum += group_value;
n = n - 3;
}
if (groups_sum >= 1000) {
string new_number = to_string(groups_sum);
return isNumberDivisibleBy37(new_number, new_number.length());
} else {
return groups_sum % 37 == 0;
}
}
int main() {
string number = "4048675309";
if (isNumberDivisibleBy37(number, 10)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
ผลลัพธ์
Yes
คำอธิบายตัวอย่าง
4048675309 → จัดกลุ่ม: 4|048|675|309 → 4 + 48 + 675 + 309 = 1036 → 1|036 → 1 + 36 = 37 → หาร 37 ลงตัว
สรุป
เทคนิคการจัดกลุ่มหลัก (Digit Grouping) ใช้ได้กับตัวหารที่ 10ᵏ ≡ 1 (mod m) เช่น 3, 9, 11, 37, 101 เป็นต้น
