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

Автор powqer, 13 лет назад, По-русски

Какое наименьшее число n можно представить в виде произведения n = a∙b ровно k способами? Произведения a∙b и b∙a считаются одним способом, все числа натуральные (1 ≤ k ≤ 50).
Лимит времени: 1 секунда
Лимит памяти: 64 MB

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

Заранее спасибо.
Задача взята отсюда: http://www.e-olimp.com/problems/5

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

13 лет назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится
Лучшее решение этой задачи - выбросить компьютер и купить велосипед!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Теперь-то что не так?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    два раза повторенная шутка - уже не шутка

    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      ... а мем.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится
      Она меня и в первый раз не улыбнула :о
      • 13 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится
        Вся улыбка на аватарку ушла, ничего не осталось? :)
        На самом деле, интересно, сколько раз freopen создавал тред "памагите ришить зодачу", пока был совсем зеленым?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Если я правильно помню - ни разу. Сначала я не знал, что вообще можно спросить и сидел над некоторыми задачам по неделе, но решал. Потом, если я не мог найти в своем коде ошибку, то никто другой тоже не мог.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну эта уже лучше.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Очевидно, нам надо найти минимальное число, имеющее 2k и 2k+12k-1 делитель, и выбрать из них минимальное. Обозначим число делителей за x. Разложим x на множители всеми возможными способами (при данных ограничениях их не очень много), дальше каждому множителю припишем простое число. Очевидно, надо приписывать минимальные простые числа, причем так, чтобы меньшим простым числам соответствовали большие количества. Если непонятно, спрашивайте, уточню.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Может 2k и 2k - 1 всё-таки?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Извините, я не понял. Допустим, мне надо получить наименьшее число, которое раскладывается 50 способами. У него будет около 100 делителей(101-если это число - квадрат, насколько я понимаю). А теперь мне необходимо найти делители 100?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Нет, перебрать все разложения 100 на множители. Понятно, что будет не более 6 множителей, каждый можно выбрать не более, чем 9 способами, т.е. не очень много. Также можно заметить, что если множителей много, то ответ будет очень маленький и его можно перебирать.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если n = p1a1 * ... * pkak, то у n (a1 + 1) * ... * (ak + 1) делителей.
  • 13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    В общем, немного подокомментирую ( powqer прошел велосипедный тест).
    Пусть есть некоторое число

    a = p1a1p2a2p3a3... pnan

    Количество его делителей



    не зависит от простых чисел в разложении a.

    Теперь. Если у числа c делителей, то подобных разложений c / 2⌉, значит, число делителей искомого числа 2k или 2k-1.

    Для заданного количества делителей надо перебрать все невозрастающие разложения в произведение сомножителей и использовать их без единицы как степени для 2, 3, 5, 7, 11, ... соответственно. Лучшее найденное число будет ответом.

    Так, если k = 2, то делителей у искомого числа 3 или 4.
    3 = 3, это соответствует 23 - 1 = 4.
    4 = 4, это соответствует 24 - 1 = 8.
    4 = 2*2, это соответствует 22 - 1 * 32 - 1 = 6.
    Ответ 4.

    P.S. http://www.e-olimp.com/problems/5
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Совершенно верно, задачка наша и к счастью, она не в перечне задач из проходящей сейчас ДЛКШ-2011.

      А вообще вопрос ко всем: а уверены ли Вы что в это время в каком-нибудь другом месте эта задачке где-то не играет?
      Кстати, как и прошлая геометрическая задачка Петра Митричева из acmp.ru ?

      Вопрос второй: а как же авторские права? На Codeforces прописано, что Вы бережёте авторские права задач, размещённых на Вашей платформе и никоим образом их нельзя использовать на других платформах.
      А в данном случае почему нет уважения к авторским правам другой платформы?

      Этот пост не с точки зрения предъявления претензий, а так, как любит писать anonymous - "задачка просто для подумать..." :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        2)Я вот только не понял, это ко мне относится? Если да, то я не имею право публиковать текст задачи без ссылки на Ваш сайт?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          По-хорошему, если подумать... ДА!
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Прокрутите на сайте любую страничку к самому низу и там найдите строку: "Все материалы, размещенные на сайте, являются собственностью их авторов и могут использоваться только с их согласия."
          Неужели она ни о чём Вам не говорит?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится
          Ну лично я считаю, что в любом случае давать ссылку на источник правильно:
          1. Некоторые личности совершенно не умеют даже правильно копипастить
          2. Можно прогнать свой код на тестирующей системе
          3. Можно определить, не идет ли сейчас контест с этой задачей
          4. Нет ли там форума, на котором разжевано до мелочей и куда можно просто дать ссылку
          и т.д.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Совершенно верно. Нет, мы ничего против размещения задач и разборов идей решений не имеем.
            Просто реально я полностью поддерживаю тех, кто не отвечает на подобные вопросы. Ибо положительный ответ в большинстве случаев это "медвежья услуга".
            Идея решения (основная теорема арифметики) указана на сайте.
            Так неужели трудно было самому поискать что это за штука и как её реализовать?
            А зачем? Гораздо проще задать вопрос на любом сайте для программистов и там процентов на 50 может и ответят, а на Codeforces этот процент вероятности получения ответа намного больше.
            Так зачем самому голову напрягать, если это могут сделать другие товарищи?  :)

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ссылку я запостил.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Дело не в ссылке, да и претензий лично к Вам у меня нет.
                Скорее претензии к явлению "группового решательства", как явлению...  :)
                • 13 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  А что Вы имеете против такого "решательства"? Мне действительно интересно было решить эту задачу, но я, подумав некоторое время, не смог. Поэтому обратился за помощью. Друзей, знакомых, которые могли бы мне помочь, у меня нет.
                  • 13 лет назад, # ^ |
                    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

                    ==============================================
                    Эта задача - немного издевательство. Данное утверждение известно как теорема (А-Б-В) и самое короткое доказательство его занимает 40 страниц. Вы, видимо, не решите ее. Но много пользы принесет размышление над ней.

                    Забытый мною автор учебника по теории чисел.
                    Подсказка к одной из задач для самостоятельного решения.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Да. Если скопипастили. Если бы изложили суть вопроса своими словами - никакого нарушения бы не было. Хотя бы потому, что задача уже стала классической.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        > На Codeforces прописано, что Вы бережёте авторские права задач, размещённых на Вашей платформе и никоим образом их нельзя использовать на других платформах.
        Где это написано? Чтобы такое написать, у CF должен быть договор с автором контеста (задачи) на передачу прав интелектуальной собственности, нет?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        Поэтому после этого что-то заявлять об авторских правах - глупо. Кроме того, это глупо хотя бы потому, что под использованием подразумевается использование задачи на каком-либо соревновании. В данном же случае задача никем и никак не используется, а просто ведется обсуждение сопутствующего ей матаппарата и подходов к решению.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        Проект лицензии как раз позволяет публиковать текст, однако обязывает рядом с ним публиковать и ссылку на CF.

        А обсуждение задач текущего соревнования если кто-то и должен отслеживать, то разве что организаторы этого соревнования. Иначе получается, что обсуждать нельзя вообще никакие опубликованные задачи — мало ли кто решил в этот момент устроить из них контест или дать в качестве домашнего задания.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится
        А на A+B у кого авторские права, если не секрет?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если Вас это утешит - вставьте текст задачи в Гугль и посмотрите на список сайтов, дружно нарушающих авторские права =)
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          Авторские права на задачу (по моему мнению, да простит меня знаток юристок!) могут распространяться только на условие и то как на литературный текст.
          Например, алгоритмы, детали реализации, участки кода не могут быть запатентованы на территории РФ.
          -----edit-----
          Имеется ввиду авторское право "вам нельзя делать то же самое, засужу!"
          Копипаста - это другой вопрос.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            С юридической точки зрения я это прекрасно знаю (хотя сам не люблю юристок =). Пытался показать это г-ну AWPRIS более наглядно.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +15 Проголосовать: не нравится
              Юристок у нас знает насквозь и не любит известно кто.
            • 13 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              Имел в свое время возможность учить в колледже информатике - очень милые ребята и девчата. И программировали иногда не хуже студентов, учившихся в группах программистов... :)
              • 13 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                Про их деловые качества никто и не спорит (хотя, они может с программистами встречались, чтобы программировать не хуже? =))). Но вот как люди... Программисты в основной своей массе все же лучше.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  А это уже как аксиома!
                  (Думаю простят на с Вами юристы и юристки за саморекламу)
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Я то финансист, поэтому никакой саморекламы, выражаю независимое мнение. Среди финансистов, кстати, тоже немало с..к порядочных. Наверное, именно поэтому я, в основном, с математиками и программистами общаюсь и дружу...
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Насколько я знаю, можно патентовать идею, как "результат интеллектуальной деятельности".
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://codeforces.net/problemset/problem/27/E
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Гарантируется, что ответ не превосходит 1018
    Зря
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Эта задача немного сложнее. Тут решение выше неприменимо. Тут фиг его знает :).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Почему же?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хотя, может и пройдет...
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          До 1000 пройдет точно в связи с тем, что число разложений в неупорядоченную сумму растет медленно, и делителей не очень много.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, почему? Решение выше применимо даже для ограничений порядка 10^5, только перебор нужен несколько более аккуратный (см. ссылку ниже на пример задачи)
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Можете для разминки решить вот эту мою задачу на ту же тему (с несколько более интересными ограничениями): http://acm.sgu.ru/problem.php?contest=0&problem=473
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Хм... похоже на динамику (делитель исходного числа, минимальное простое число в разложении)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Попробуйте сдать так - мне самому интересно, зайдет или нет.
      Авторское решение - все тем же перебором, только более аккуратным =)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Очень лениво кодить. На работе хватает)
        Делителей исходного числа не больше 1000.
        В среднем у них делителей мало будет.
        Динамика ленивая. Числа длинные. Для ускорения используется расчет рядом в логарифмах.
        100% заходит.