Разбор задачи D
Условия задачи четвертого тура
Пусть n – исходное число. Если n=1, то ответом является 1. Иначе будем нам необходимо представить n в виде произведения нескольких чисел (цифр) от 2 до 9.
При этом нам необходимо чтобы суммарное количество цифр было как можно меньше (тогда удастся составить меньшее число), кроме того, желательно использовать как можно бoльшие цифры, тогда другие цифры получатся меньше и также можно будет составить меньшее число. Например, если необходимо представить требуемым образом число 24, то лучше использовать делитель 8, т.к. тогда удастся представить число 24=3*8. Если же не использовать делитель 8, а использовать делитель 6, то получится худшее представление: 24=4*6.
Таким образом, будем делить число последовательно на цифры 9, 8, 7, 6, 5, 4, 3, 2, пытаясь получить в разложении большие цифры. Для нахождения минимального числа полученные цифры необходимо будет записать в обратном порядке.
Также следует учесть проблему переполнения результата: например, если исходное число равно 510=9765625, то правильный ответ будет иметь вид 5555555555, и его невозможно будет записать в переменной типа int. Поэтому результат будем записывать в строку Result.
int n;
cin >> n;
// Отдельно разберем случай n==1
if(n==1)
{
cout<<1<<endl;
return 0;
}
string Result; // Для записи ответа
int digit; // Переменная – перебираемая цифра
// Цикл по всем цифрам от 9 до 2
for(digit=9;digit>=2;--digit)
{
// Будем делить число n на цифру digit пока это возможно
while(n%digit==0)
{
n/=digit;
// Цифру digit дописываем в начало строки Result
Result=(char)('0'+digit)+Result;
}
}
// Если в результате не получилось число 1, то n имеет простые делители, большие 9
// поэтому выведем 0, иначе выведем всю строку Result
if(n!=1)
cout<<0<<endl;
else
cout<<Result<<endl;