ในปัญหานี้เราจะพยายามหาเลข K หลักที่เล็กที่สุด ที่จะหารด้วย X ลงตัว เพื่อทำงานนี้ เราจะ取เลข K หลักที่เล็กที่สุดด้วยสูตร (10^(k-1)) จากนั้นตรวจสอบว่าตัวเลขหารด้วย X ลงตัวหรือไม่ ถ้าไม่ เราจะได้ตัวเลขที่ถูกต้องโดยใช้สูตรนี้
(min + X) - ((min + X) mod X)
ตัวอย่างหนึ่ง คือ เลข 5 หลัก ที่หารด้วย 29 ลงตัว เลข 5 หลักที่เล็กที่สุดคือ 10000 ไม่หารด้วย 29 ลงตัว ตอนนี้ใช้สูตรจะได้ −
(10000 + 29) - ((10000 + 29) mod 29) = 10029 - 24 = 10005
เลข 10005 หารด้วย 29 ลงตัว
อัลกอริทึม
minKDigit(k, x)
begin
min = 10 ^ (k-1)
if min is divisible by x, return min
otherwise return (min + x) - ((min + x) mod x)
end
ตัวอย่าง
#include<iostream>
#include<cmath>
using namespace std;
long min_k_digit(int k, int x) {
// get the minimum number of k digits
int min = pow(10, k-1);
if(min % x == 0) {
return min;
}
return (min + x) - ((min + x) % x);
}
int main() {
int k, x;
cout << "Enter Digit Count(K) and Divisor(N): ";
cin >> k >> x;
cout << "Result is: " << min_k_digit(k, x);
}
ผลลัพธ์
Enter Digit Count(K) and Divisor(N): 5 29 Result is: 10005
ผลลัพธ์เพิ่มเติม
Enter Digit Count(K) and Divisor(N): 6 87 Result is: 100050
