Smallest Divisible Number
National Olympiad — Regional round (2018 season)
Submission name: beautiful.cpp
Problem summary
Find the smallest positive n-digit decimal integer divisible by k. If no n-digit multiple exists, report NO.
Input
Two integers n and k.
Output
The smallest n-digit multiple of k, or NO.
Constraints
1 ≤ n ≤ 18; 1 ≤ k ≤ 10000000.
Worked example
An independently prepared example for this explanation.
Input
2 3
Output
12
Solution analysis
- The smallest n-digit number is lower=10^(n−1), and the largest is 10·lower−1. We need the first multiple of k at or above lower.
- Compute the remainder lower%k. If it is zero, lower already works; otherwise add k−remainder. Finally check whether the candidate remains below 10·lower.
- For n=3 and k=6, lower=100 and its remainder is 4, so add 2 to get 102. For n=1 and k=11, the candidate is 11, which has too many digits, so no solution exists.
Why it works
The multiples of k are spaced exactly k apart. Adding zero or k−lower%k reaches the first multiple not below lower. Every n-digit solution must be at least this candidate, and the upper-bound check accepts it exactly when it still has n digits.
Watch out. Use integer multiplication to form powers of ten. A signed 64-bit type safely holds 10¹⁸ and the candidate under these bounds.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
long long k;
cin >> n >> k;
long long lower = 1;
for (int digit = 1; digit < n; ++digit) {
lower *= 10;
}
long long candidate = lower;
// Advance to the first multiple without skipping an already divisible lower bound.
if (lower % k != 0) {
candidate += k - lower % k;
}
if (candidate < lower * 10) {
cout << candidate << '\n';
} else {
cout << "NO\n";
}
}