Задача «Счастливые цифры» РОИ 2008 Автор задачи: научный комитет РОИ Разбор: Андрей Сергеевич Лопатин

Полный перебор: 45 баллов Перебираем все системы счисления с основанием от 2 до n + 1 Для каждой из систем счисления c основанием 2 d n + 1 переводим число в эту систему и смотрим количество цифр k на конце. Время работы: O(n)

Правильные решения (100 баллов) Решение с перебором делителей числа n – k (O(sqrt (n))) Решение с перебором всех систем счисления до sqrt (n), а затем n – k и (n – k) / k

Особые случаи n < k: все системы счисления равнозначны n = k: ответом является любая система счисления с основанием более k Невозможно найти такое основание, что число заканчивается цифрой k (например, тест из условия 7 5)

Перебор делителей Реализация 1: перебрать все делители до sqrt (n), а остальные имеют вид n / d i, где d i – некоторый делитель <= sqrt (n) Реализация 2: разложить на простые множители, а затем перебрать все комбинации множителей

Перебор оснований до sqrt (n) Если в числе более двух цифр k, то k*d*d < n Если в числе одна цифра k, то подходит d = n – k Если две цифры k, то k * d + k = n, следовательно (n – k) / k = d Особый случай: k = 0

Разбор окончен??? 1 message(s) pending… Bonus track!

Решение за O(n 1/3 ) (+ баллов) Аналогично перебору всех d <= sqrt (n), переберём d <= n 1/3 Остались случаи: одна, две, три цифры k в конце числа Отдельно разберём n – k, (n – k) / k Однако, число может иметь вид zkk d, где z – некоторая цифра. При этом может быть как z = k, так и z k.

Решение за O(n 1/3 ) (+ баллов) Как рассмотреть zkk d ? Зафиксируем z, тогда z * d 2 + k * d + k = = n. Решаем квадратное уравнение – его положительный корень и есть значение d. Ясно, что z n 1/3. Можно ли быстрее?

Как быстрее? Кажется, что можно также разобрать все d до n 1/4, а затем решать уравнение (кубическое?) Но тогда придется перебирать числа вида yzkk d, где y и z порядка n 1/4. Их уже sqrt (n). Таким образом, кубическое решение наиболее быстрое из этой серии.

Разбор задачи окончен Спасибо за внимание! Успехов!