Small Divisors of a Huge Integer
National Olympiad — National round
Submission name: div.cpp
Problem summary
For a positive decimal integer N, list every divisor d with 1 < d < 2001 together with the exact quotient N/d.
Input
The decimal representation of N.
Output
One line d N/d per divisor, in increasing d order.
Constraints
2 ≤ N ≤ 10^100; at least one qualifying divisor exists.
Worked example
An independently prepared example for this explanation.
Input
10
Output
2 5 5 2 10 1
Solution analysis
- Store N as a string. For each possible divisor perform decimal long division.
- The running remainder fits in an integer. Emit the quotient only if the final remainder is zero, removing leading quotient zeros.
Why it works
Long division maintains the quotient and remainder of every processed prefix. A final zero remainder is exactly divisibility, and the accumulated quotient is exact.
Complexity: O(2000 × digits(N)) time, O(digits(N)) extra space.
Watch out. N may have 101 digits. Include divisor N itself when N ≤ 2000.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Long division maintains the quotient and remainder of every processed prefix. A final zero
// remainder is exactly divisibility, and the accumulated quotient is exact.
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
for(int d=2;d<=2000;d++){
int rem=0;
string q;
for(char c:s){
rem=rem*10+c-'0';
q+=char('0'+rem/d);
rem%=d;
}
if(rem==0){
size_t p=q.find_first_not_of('0');
cout<<d<<' '<<(p==string::npos?"0":q.substr(p))<<'\n';
}
}
}