Agent’s Safe Number
Autumn Tournament (2025)
Submission name: agent.cpp
Problem summary
Find the smallest positive integer whose decimal digits have product K. If no such number exists, print XXX. The answer may have more digits than a machine integer can hold.
Input
One positive integer K.
Output
The smallest safe number, or XXX.
Constraints
1 ≤ K ≤ 1000000000000000000.
Worked example
Original statement sample.
Input
1024
Output
2888
Solution analysis
- For K=1, the answer is 1. Otherwise digits 0 and 1 cannot help: zero destroys the positive product, and one adds length without changing it.
- Repeatedly divide K by 9,8,...,2, storing each successful divisor as a digit. If any factor remains, it must contain a prime other than 2,3,5,7 and no decimal digit can represent it. Sort the collected digits increasingly to minimize the resulting number.
- For 1024, division extracts 8,8,8,2. Writing them as 2888 gives product 1024. For 51, the factor 17 remains and the answer is XXX.
Why it works
A minimum number first minimizes digit count. Factors 5 and 7 are forced. For the remaining factors 2 and 3, combining 3·3 into 9, 2·2·2 into 8, and 2·3 into 6 reduces digit count; ties such as 2·6 versus 3·4 favor the digits selected by descending extraction. After these combinations, ascending order is the smallest arrangement of that multiset.
Watch out. Do not store the answer in long long: K fits, but its digit representation need not. K=1 needs a special case.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main(){
long long product;
cin>>product;
if(product==1){
cout<<1<<'\n';
return 0;
}
string digits;
// Large composite digits pack several prime factors into one place.
for(int digit=9;digit>=2;digit--){
while(product%digit==0){
digits.push_back(static_cast<char>('0'+digit));
product/=digit;
}
}
if(product!=1){
cout<<"XXX\n";
return 0;
}
sort(digits.begin(),digits.end());
cout<<digits<<'\n';
}