ในบทความนี้ เราจะอภิบายการหาจำนวนหน่วยที่ซ้ำ (Repeated Units) ที่หารด้วย N ลงตัว Repeated units คือตัวเลขที่ประกอบด้วยเลข 1 เท่านั้น ให้ R(k) เป็น repeated unit ที่ k คือความยาวของเลข 1 เช่น R(4) = 1111 เราต้องหาค่า k น้อยที่สุดที่ทำให้ R(k) หารด้วย N ลงตัว เช่น:
Input : N = 13 Output : k = 6 Explanation : R(6) คือ 111111 หาร 13 ลงตัว Input : N = 31 Output : k = 15
แนวทางแก้ปัญหา
คุณอาจคิดว่าจะลองทุก k ตั้งแต่ 1 จนกว่า R(k) จะหาร N ลงตัว แต่จะไม่รู้ว่า N หาร R(k) ไม่ลงตัวสำหรับ k ใดๆ ทำให้ซับซ้อน
แนวทางที่มีประสิทธิภาพ:
- ตรวจสอบว่า N เป็น coprime กับ 10 หรือไม่ (คือ N ไม่หาร 2 และ 5 ลงตัว)
- ถ้า ไม่ใช่ coprime → R(k) จะไม่เคยหาร N ลงตัวสำหรับ k ใดๆ
- ถ้า ใช่ coprime → สำหรับ R(1), R(2), R(3)... คำนวณเศษของ R(i) หาร N จะได้ n ค่าเศษ
- หาเศษที่ซ้ำกันของ R(i) และ R(j) ทำให้ R(i) - R(j) หาร N ลงตัว
- ความต่างของ R(i) และ R(j) จะเป็น repeated unit คูณกำลังของ 10 แต่ 10 และ N เป็น coprime ดังนั้น R(k) จะหาร N ลงตัว
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int main() {
int N = 31;
int k = 1;
// ตรวจสอบว่า N เป็น coprime กับ 10
if (N % 2 == 0 || N % 5 == 0) {
k = 0;
} else {
int r = 1;
int power = 1;
// ตรวจสอบจนกว่าเศษจะหาร N ลงตัว
while (r % N != 0) {
k++;
power = (power * 10) % N;
r = (r + power) % N;
}
}
cout << "Value for k : " << k;
return 0;
}
ผลลัพธ์
Value for k : 15
สรุป
ในบทความนี้ เราอภิบายการหาค่า k สำหรับ R(k) โดยที่ R(k) คือ repeated units ที่หาร N ลงตัว เราอภิบายวิธีที่มีประสิทธิภาพพร้อมโค้ด C++ สามารถเขียนในภาษาอื่นได้เช่น Java, C, Python หวังว่าจะเป็นประโยชน์
