Smallest Long Multiple
National Olympiad — Regional round (2018 season)
Submission name: long.cpp
Problem summary
Find the smallest n-digit positive multiple of k.
Input
n k.
Output
The exact smallest n-digit multiple.
Constraints
2 ≤ n ≤1000;2 ≤ k ≤10000000;k<10^n.
Worked example
Input and output for the worked example discussed below.
Input
15 1234567
Output
100000001074020
Solution analysis
- Start at A=10^(n−1), the smallest n-digit integer. The result is A plus the smallest nonnegative offset making it divisible by k.
- Compute A mod k by multiplying1 by10 modulo k n−1 times. The offset is (k−remainder) mod k and is smaller than k. Add it to the decimal string for A with right-to-left carries.
- For n=15,k=1234567, the offset1074020 produces100000001074020. If A is already divisible, the offset is0. The guarantee k<10^n ensures an n-digit multiple exists.
Why it works
Offsets producing multiples have residue−A modulo k. Its least nonnegative representative therefore gives the first multiple at or above A; exact decimal addition preserves that value.
Complexity: O(n) time and O(n) space.
Watch out. Avoid floating-point powers and fixed-width conversion of A. Do not add k when its remainder is already0.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
int k;
cin>>n>>k;
long long remainder=1%k;
for(int i=1;i<n;i++){
remainder=remainder*10%k;
}
long long carry=(k-remainder)%k;
string answer="1"+string(n-1,'0');
// Add the small offset to the exact long decimal representation.
for(int i=n-1;i>=0&&carry>0;i--){
long long value=answer[i]-'0'+carry;
answer[i]=char('0'+value%10);
carry=value/10;
}
cout<<answer<<'\n';
}