ภาพรวมปัญหา
ให้ช่วง [START, END] ต้องการนับจำนวนในช่วงที่หารหลักไม่ใช่ศูนย์ของตัวเองลงตัวทุกหลัก
ตัวอย่าง
Input: START=10, END=20
Output: 14 (โค้ดต้นฉบับแสดง 14 แต่ตัวอย่างอธิบาย 5 ตัว: 10,11,12,15,20)
หมายเหตุ: ผลลัพธ์ตัวอย่างและคำอธิบายไม่สอดคล้องกัน โค้ดนับได้ 14 ตัว
Input: START=100, END=200
Output: 25
แนวทางแก้ปัญหา
- วนลูป i จาก START ถึง END
- แยกหลักของ i ด้วย while loop
- ถ้าหลัก > 0 และ i หารหลักนั้นไม่ลงตัว → ไม่ผ่าน
- ถ้าผ่านทุกหลัก ให้เพิ่ม count
โค้ดตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int divisiblebyDigits(int start, int end) {
int count = 0;
for (int i = start; i <= end; i++) {
int num = i;
bool ok = true;
while (num > 0) {
int digit = num % 10;
if (digit > 0 && i % digit != 0) {
ok = false;
break;
}
num /= 10;
}
if (ok) count++;
}
return count;
}
int main() {
int START = 10, END = 50;
cout << "Count: " << divisiblebyDigits(START, END);
return 0;
}
ผลลัพธ์
Numbers that are divisible by all its non-zero digits: 14
การปรับปรุงและข้อสังเกต
- ตัวอย่าง START=10, END=20 ควรได้ 5 (10,11,12,15,20) แต่โค้ดแสดง 14 — อาจมี bug หรือช่วงต่างกัน
- ใช้ flag แบบ boolean แทน int 0/1 อ่านง่ายกว่า
- break ทันทีที่เจอหลักที่หารไม่ลงตัว
แนวทาง Digit DP (สำหรับช่วงใหญ่)
นับจำนวนใน [0, X] ที่หารหลักไม่ศูนย์ลงตัว ใช้ DP state: pos, mod2520, lcm_of_digits, tight
เพราะ LCM(1..9) = 2520 สามารถลด mod เหลือ 2520 ได้
ความซับซ้อน
- Brute Force: O((END-START) × log₁₀END)
- Digit DP: O(log END × 2520 × 48 × 2) — ใช้ได้กับ END ≤ 10¹⁸
ลำดับตัวเลขที่มีคุณสมบัตินี้ (Self-dividing numbers / OEIS A034838)
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22, 24, 33, 36, 44, 48, 55, 66, 77, 88, 99, 111, 112, 115, 122, 124, 126, 128, 132, 135, 144, 155, 162, 168, 175, 184, 212, 216, 222, 224, 244, 248, 264, 288, 312, 315, 324, 333, 336, 366, 384, 396, 412, 424, 432, 444, 448, 488, 515, 555, 612, 624, 636, 648, 666, 672, 684, 715, 728, 735, 777, 784, 812, 816, 824, 848, 864, 888, 936, 999...
