Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 
Вернуться
Тема: Задача 1781.
1
  1  Неизвестный, 12 апреля 2021 г. 14:17:42
      <a href="https://linktr.ee/FORWIN77">FORWIN77</a> merupakan situs slot online terbaik di indonesia yang memiliki beragam jenis permainan slot online yang terlengkap. Dan juga menyediakan deposit pulsa tanpa potongan.
  2  Хворых Павел, 29 марта 2021 г. 18:11:22
      Можно и точный номер числа Фибоначчи найти, если посчитать логарифм X:
mantissa = float(X[0] + '.' + X[1:20])
exponent = len(X) - 1
logX = log10(mantissa) + exponent
phi = (1 + sqrt(5))/2
k = round((logX + log10(5)/2)/log10(phi))
Дальше сравнить X и k-е число Фибоначчи по модулям 10^18 и 9, такое решение проходит все тесты и не требует вообще никакой длинной арифметики. Ну или можно взять случайный модуль порядка 10^18, такое решение требует тривиального алгоритма деления длинного на короткое, а вероятность Wrong answer почти нулевая.
  3  Странник, 27 марта 2021 г. 16:39:27
      Если кому интересно, можете прочитать про китайскую теорему об остатках (хотя я уверен, что многие знают про неё). Как вариант, представить исходное число n в виде остатков от деления на m взаимно простых чисел (то есть число n будет как вектор из m элементов). Далее можно элементы матрицы [[1,1],[1,0]] представить в таком же виде, возвести эту матрицу в степень k, где k - приблизительный номер числа Фибоначчи, полученный из формулы Бине. Прелесть такого представления чисел в том, что сложение, вычитание и умножение производится за O(m). А решение с полиномиальными хешами - это урезанный вариант этого решения, как я понимаю. Достаточно взять несколько простых модулей, чтобы решение прошло.
  4  Яндулов Богдан, 25 марта 2021 г. 17:58:13
      А как же хеши?)
  5  Лукьянчиков Владимир Игоревич, 25 марта 2021 г. 8:32:37
      Тер-Саркисов Богдан Олегович теперь Странник? -;)
1615 задача против 1621 - это уже серьезно!
  6  Лукьянчиков Владимир Игоревич, 25 марта 2021 г. 8:16:55
      Изначально, когда создавалась задача, была такая же идея с полными квадратами. Т.к. корень достаточно "дорогая" операция, было решено определять по длине числа диапазон чисел Фибоначчи (максимум 5). Быстро получить число Фибоначчи можно либо через единичную матрицу с быстрым возведением в степень, либо через рекурсивную функцию, использующую тождества чисел Фибоначчи.
  7  Странник, 24 марта 2021 г. 23:30:25
      О, как замечательно! Но интересно, как решать подобное на c++
  8  Чернышов Андрей Максимович, 24 марта 2021 г. 23:27:28
      Идея точно такая же, только использовал метод math.isqrt(), доступный с 3.8.
  9  Странник, 24 марта 2021 г. 23:23:36
      А можно полюбопытствовать насчет идеи вашего решения? Моя идея: проверить, что хотя бы одно из чисел 5*n**2-4 и 5*n**2+4 является полным квадратом (факт лично не доказывал, погуглил). Извлекал целочисленный квадратный корень методом Ньютона.
  10  Чернышов Андрей Максимович, 24 марта 2021 г. 23:09:30
      На питончике задача явно не стоит своих 88% :)
  11  Странник, 24 марта 2021 г. 22:45:57
      Конечно. Знать бы еще нормальное решение.
  12  Лукьянчиков Владимир Игоревич, 24 марта 2021 г. 22:16:12
      Понравилась?
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2021, E-mail: admin@acmp.ru