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

Тяжёлая задача с сайта www.e-olimp.com.
Автор scorpion, 13 лет назад, По-русски

Дорогие Программисты. Многие из вас возможно слышали задачу про лампочки, и , наверное, её решили.

Мне очень нужна ваша помощь в решении похожей задачи. А вот и она: http://www.e-olimp.com/problems/1906.

Может кто нибудь знает как её решать?

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

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
интересно стало, как она решается:)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1018 < 263 - 1
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, когда n<=10^18, она легко решается))
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

        Не имеет значения, меньше ли N 10^18
        Количество погашенных лампочек - количество чисел, у которых нечетное число делителей. Пусть a1, a2, ... , ak - степени в разложении на простые. Тогда у числа (a1 + 1) * (a2 + 1) * ... (ak + 1) делителей. Чтобы это число было нечетным, все числа (ai + 1) , etc должны быть нечетными. Значит все ai - четные. То есть все они больше 2. То есть на это число не влияет то, включали ли лампочки в честь человека с номером большим корня из N
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Если я неправ, скажите в чем, плиз
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            т.е. ответ, по твойму, целая часть от корня из n (trunc(sqrt(n))?
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Нет. По-моему мы можем не 10^18 раз, а N прощелкать, при N не сильно больших 10^18
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                9x1018 вряд ли можно назвать не сильно большим 1018. И N раз мы тут щелкать не можем. 

                Например, если возьмем простое P > 1018 и умножим его на 2, то у этого числа будет только 1 делитель <= 1018 и это число нужно включить в ответ
                → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Мы посчитаем количество выключенных (оно не изменится!) и вычтем его из N ;)
                  → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да уж, согласен
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://codeforces.me/blog/entry/1434
это была задача А.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Может кому вдруг станет интересно (особенно из тех, кто не принимал участие в Зимней Школе 2011), выложил "оригинальный" разбор из Харькова. З.Ы. Правда, весит он 64 мб:)
Разбор ведет Ельдар Богданов (gojira)
http://webfile.ru/5432832


→ Ответить