Блог пользователя tamir

Помогите решить задачу...
Автор tamir, 11 лет назад, По-русски

Здравствуйте! Помогите решить данную задачу ( http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302 ). Спасибо за помощь!

Problem solved.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Почитайте про Функцию Эйлера, далее я бы решал так: посчитаем эту функцию для знаменателей до максимально возможного, а потом бин поиском по суммам на префиксе ищем нужный знаменатель, потом линейным поиском находим нужный числитель.

P.S. Можно заметить из теста из условия, что максимальный знаменатель = 200000.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо за ответ! Мне тоже это решение пришло , но я подумал , что оно не пройдет по времени)

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Не люблю задачи, в которых не даны все ограничения, вот тут, например, не ясно сколько тестов и от этого зависит, пройдет ли.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Спасибо за совет , задача прошла )

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Бин поиском по суммам искал или линейным поиком?

          → Ответить
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Как вы написали выше : бин поиском по суммам на префиксе ( знаменатель ) и линейным поиском ( числитель )

            → Ответить