Разбор задачи 455 acmp.ru Умножение дроби. Решение на C++
Вставка
- Опубліковано 16 гру 2024
- Теги: длинная арифметика,умножение длинного на короткое,добавление короткого к длинному,выделение периода
О проекте "3.5 задачи в неделю": разбор олимпиадных задач по программированию каждые 2 дня в прямом эфире в 10 вечера по Москве. Более подробно goo.gl/qa142q
В проекте разобрано более 250 задач acmp.ru, общая длина видео разборов более 150 часов.
Список всех разборов, доступных участникам проекта, приведён в таблице goo.gl/WaMLu1 В седьмом столбце указаны теги - темы задач. Как стать участником проекта, написано в статье goo.gl/sUTIgo Участие бесплатно.
Ведущий проекта Меньшиков Фёдор Владимирович, автор книги "Олимпиадные задачи по программированию".
Разборы более простых задач в проекте "Олимпиадное программирование с нуля на Java" / @java4869
По поводу индивидуальных занятий по подготовке к олимпиадам обращайтесь по адресу mfv@mail.ru
Очень хорошо объясняете решение задач в том числе и данной задачи тоже! Но вот не ясно только одно, почему мы ищем длину нового периода среди ДЕЛИТЕЛЕЙ числа длины старого периода?
Представим себе много блоков цифр, каждый из которых - период исходного числа. Когда мы начнём умножать этот период на второе число, результат умножения зависит только от переноса из предыдущего блока. Причём если перенос в блок увеличивается, перенос из блока не может уменьшиться. И при этом перенос меньше числа, на которое умножаем. Получается, что этот перенос со временем стабилизируется - и период результата умножения будет совпадать с периодом исходного числа. Возможно, это будет не минимальный период, но это точно будет период. Если предположить, что минимальный период не делитель исходного периода, то мы отсюда получим, что исходный период не будет периодом ответа, а это не так.
Можно ли с помощью префикс-функцией найти период в последовательности чисел, если да то что будет работать быстрее, поиск периода с префикс-функцией или же поиск периода по вашему коду?
Префикс-функцией чистый O(n), где n - длина старого периода. Разумеется лучше, чем O(n * div(n)), где n - длина старого периода, а div - количество делителей n.
Спасибо за ответ!