Здравствуйте, bkat, Вы писали:

IO>>А что такое полиномиальное время?

B>Это означает, что требуемое время оценивается полиномом от входных данных.

Маленькое добавление:
длина входных данных в данной задаче по определению = число цифр в (десятичной) записи числа.