Convert a Hundred-Digit Base-p Number
National Olympiad — Regional round (2024 season)
Submission name: number.cpp
Problem summary
Convert a positive base-p number to its exact decimal representation even when it exceeds built-in integer types.
Input
The digit string and base p.
Output
The decimal number.
Constraints
2≤p≤9; at most 100 base-p digits.
Worked example
Input and output for the worked example discussed below.
Input
1234512345123451234512345 6
Output
6819612498497606825
Solution analysis
- Read the number as a string. Horner’s rule updates value=value×p+digit for each source digit, avoiding large powers.
- Store the decimal value as reversed decimal digits. Multiply each by p, add carry, and append all remaining carry digits. Only small-integer multiplication is required.
- For 123 base 6, values evolve 1, then 1×6+2=8, then 8×6+3=51. The same exact process handles the longer official sample.
Why it works
After each source prefix, the vector is its decimal value. The next positional digit means multiplying by p and adding it; decimal carry propagation implements that identity exactly.
Complexity: O(L²) time and O(L) auxiliary space for L source digits.
Watch out. Do not parse the whole string into an integer or use floating-point powers. Print the stored digits in reverse order.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
string number;
int base;
cin>>number>>base;
vector<int>decimal(1,0);
for(char character:number){
int carry=character-'0';
// Horner evaluation with exact little-endian decimal digits.
for(int&digit:decimal){
int value=digit*base+carry;
digit=value%10;
carry=value/10;
}
while(carry>0){
decimal.push_back(carry%10);
carry/=10;
}
}
for(auto it=decimal.rbegin();it!=decimal.rend();it++){
cout<<*it;
}
cout<<'\n';
}