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

Помогите с задачей!
Автор dyussenaliyev, 13 лет назад, По-русски


Заранее спасибо!

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

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

ну видимо верен такой факт, что где φ функция ейлера.

edit если
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится
    В решении жури я видел что-то похожее, тоже с функцией Эйлера, но так и не понял почему? Объясните пожалуйста почему именно так?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      см. http://ru.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну я могу объяснять это словами "мультипликативная группа обратимых по модулю t имеет порядок φ(t) значит для любого " незнаю насколько они хорошо объясняют это :)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А тут недавно daftcoder говорил, что математика не нужна для программирования - а смотрите, как Коля бойко решает задачи на теорию чисел ^_^
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Программирование (промышленное) и олимпиадные задачи - кагбэ совсем разные вещи. Лучше вчитываться надо было, или не писать такого.
          → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

            Венгерский метод в промышленном коде никогда не видели?

            Дейкстру на сжатом пространстве?
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              ==============================
              Сжатое пространство ~ разреженный граф? о_О

              Вы решили меня матчастью раздавить? :D

              Венгерский алго. в промышленном коде пока ни разу не видел, и не знаю увижу ли. Уж не знаю на сколько должна быть велика размерность матрицы (и кто её будет составлять О_о) чтобы там поток не зашел.
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                В промышленном коде я думаю нет понятие "не зайдёт" )) наверно главное это время само по себе а улучшения в два раза это уже прогресс...

                Про Венгерку все знают, что она работает за V3 это конечно чудесно, но я её никогда особо не стримился понимать... потому что есть Дейкстра с потенциалами которая на плотном работает тот-же V3 а на разряженом и то лучше и понимается в разы проще. Но есть какие-нибудь публикации на тему константы в асимптотики на случайных,худших случаях? или кто-то их просто знает ;)
                → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится
                  Там полный граф с практически идеальными для венгерки условиями.

                  Кстати, интересно проверить, что для случайной матрицы венгерка - не квадрат (вообще, мотивы есть).
                  → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Этот факт верен с небольшой оговоркой. t и 2 - должны быть взаимно просты.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да, конечно это так. в моём коментарии про a, (a, t) = 1 
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Для четных t ответ будет 0 для всех x, начиная где-то с 4.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        это не верно t = 6 четно 2k никогда не будет делится на 6
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    f(1) = 2
    f(2) = 4
    f(3) = 16
    f(4) = 65536

    f(3) mod 8 = 2^(f(2) mod 4) mod 8 = 2^(0) mod 8 = 1
    но
    f(3) mod 8 = 0

    Кажется, опровергнуто.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      кстати, а что нам мешает посчитать t = 2k2k1, k1 нечетно. После этого остаток от деления на t восстанавливается по китайской об остатках из



      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Судя по всему, это будет единственно верным решением "в лоб", использующим функцию Эйлера.
        → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Что-то с памятью моей стало.

        Кажется, для любых a и t верно утверждение



        если



        Это связано с тем, что в последовательности предпериод не превосходит степени максимального простого в t, а период после разложения t = t1t2 на часть t1, взаимно простую с a и все остальное будет совпадать по длине с периодом , делителем , делителем
        Прошу доказать строго или опровергнуть :)
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          Примитивным исходником проверил t <= 100, n < t*4, работает

          Если так, то задача решается совсем просто - надо оставлять не остаток от деления, а еще немного сверху, поскольку в прошлой формуле также допустима запись
          → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

был коммент нетуда, куда надо

→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Динамика dp(i, p) = f(i) % p, p - простое.
f(i) = 2f(i-1)%fi(p) % p.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Коммент от anonymous
    >>f(1) = 2
    >>f(2) = 4
    >>f(3) = 16
    >>f(4) = 65536

    >>f(3) mod 8 = 2^(f(2) mod 4) mod 8 = 2^(0) mod 8 = 1
    >>но
    >>f(3) mod 8 = 0

    >>Кажется, опровергнуто.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Для простых кроме 2 работает. Только не очень понятно тогда, что имеет ввиду автор изначального сообщения.
      → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      p - простое!
      Если p - не простое, раскладываем и китайская теорема об остатках.
      → Ответить