Кресты / Говнокод #27823 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}
 
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

https://codeforces.com/contest/1508/submission/113222414

> if (n == 2 || n == 7 || n == 61) return true;

Помню я как делал: подобрал 3 базовых числа, прогнал на всех интах, там где алгоритм ошибался - проифал вручную )))

Запостил: 3_dar 3_dar, (Updated )

Комментарии (44) RSS

    • .
              auto tmp = s;
              s = t;
              t = tmp;
              tmp = m0;
              m0 = m1;
              m1 = tmp;

      std::swap недостаточно перфомансно работает, да?
      Ответить
    • /**
       * code generated by JHelper
       * More info: https://github.com/AlexeyDmitriev/JHelper
       * @author
       */

      И что эта херота делает? Сшивает кучу файлов в одну единицу трансляции, чтобы можно было отправить это на олимпиадный сайт?

      // Fast modular multiplication by barrett reduction
      // Reference: https://en.wikipedia.org/wiki/Barrett_reduction
      // NOTE: reconsider after Ice Lake
      struct barrett {
          unsigned int _m;
          unsigned long long im;
       
          // @param m `1 <= m < 2^31`
          barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
       
          // @return m
          unsigned int umod() const { return _m; }
       
          // @param a `0 <= a < m`
          // @param b `0 <= b < m`
          // @return `a * b % m`
          unsigned int mul(unsigned int a, unsigned int b) const {
              // [1] m = 1
              // a = b = im = 0, so okay
       
              // [2] m >= 2
              // im = ceil(2^64 / m)
              // -> im * m = 2^64 + r (0 <= r < m)
              // let z = a*b = c*m + d (0 <= c, d < m)
              // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
              // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
              // ((ab * im) >> 64) == c or c + 1
              unsigned long long z = a;
              z *= b;
      #ifdef _MSC_VER
              unsigned long long x;
              _umul128(z, im, &x);
      #else
              unsigned long long x =
                  (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      #endif
              unsigned int v = (unsigned int)(z - x * _m);
              if (_m <= v) v += _m;
              return v;
          }
      };

      Интересно, у олимпиадников есть специальные олимпиадные библиотеки для алгоритмов и структур данных? Или они такое нахуеверчивают сами руками каждый раз, вызубрив все эти алгоритмы? Или у каждого уважающего себя олимпиадника есть свой говнонабор написанных им лично алгоритмов и структур данных, который он переиспользует в всяких разных олимпиадах?
      Ответить
      • https://github.com/xennygrimmato/Data-Structures-and-Algorithms/blob/d557c0694de9c22b22d74dd99b67abc811405ed7/fast_mod_mul_barrett_reduction/barrett_reduction.cpp


        Да, похоже что есть специальные о-ли-мпи-ад-ные библиотеки со всякой такой хуйней
        https://github.com/xennygrimmato/Data-Structures-and-Algorithms/
        > A collection of some implementations of data structures and algorithms, primarily for competitive programming.

        Или вот еще https://github.com/VandanRogheliya/Competitive-Programming-Setup/

        https://github.com/search?q=%22Fast+modular+multiplication+by+barrett+reduction%22&type=code
        дохуя находит
        Ответить
      • Смотри шапку его кода. "JHelper" - это как раз и есть плагин для "CLion", чтобы вхуеверчивать куски заготовленного кода в файл.
        Ответить
      • Фиг знает... На оффлайн олимпиадах вообще не давали свой код приносить.

        Это на онлайне можно каких-нибудь кусков по-быстрому накопипастить.
        Ответить
        • > Фиг знает... На оффлайн олимпиадах вообще не давали свой код приносить.

          Т.е. олимпиады проверяют навык быстрого наговнивания некоторой хуйни, которая бы формально проходила все тесты?

          Некоторые олимпиадные задачи заточены под использования бигинтов, а в крестах их еще не завезли, притом в каком-нибудь питоне эти бигинты есть из коробки, и поскольку в питоне не надо изобретать бигинты, писать на питоне такие задания заметно проще, чем на крестах. Не логичнее ли тогда для тех же крестов разрешить юзать какую-то бигинтовую либу? Может быть олимпиадникам надо пойти в крекстокомитет и им в пропозалы внести свои говнобиблиотеки для олимпиад? И чтоб было std::olympiad::какаятохуйня
          Ответить
  • > проифал вручную

    А теперь проифай их там, где этот primality check реально нужен... В каком-нибудь RSA 4096.
    Ответить
    • Так это всё равно вероятностный тест. Обычным перебором заебешься проверять.
      Ответить
      • Ну просто если тест сбоит даже на мелких числах, то на крупных вообще будет показывать фигню...

        Для крупных видимо надо больше базисов или формулу которая сильнее вероятность режет на каждом тесте.
        Ответить
        • Разумеется. 3 числа - это ради перформанса в олимпиадах
          Ответить
    • if 3 % 2 != 0:
          print("3 простое число")
      if 4 % 2 != 0 and 4 % 3 != 0:
          print("4 простое число")
      if 5 % 2 != 0 and 5 % 3 != 0 and 5 % 4 != 0:
          print("5 простое число")
      # итд
      Ответить
  • Q17: Why don’t you say who you are?

    A17: Spammers are criminal gangs. In 2004 and since, many other blacklists stopped after they were threatened or attacked.
    We also got a package from Ukraine with a dead rat inside and a message: "You are next!"
    For security reasons we moved to a new location and have chosen to continue our war against spammers.
    Art 34 Abs 5 BayMeldeG (Bavarian Law) grants that only national authorities can find out about us.
    Ответить
    • Добрый день, guestinho! Ваши недавние комментарии/посты/личные сообщения или другая активность на сайте нарушили правила сообщества Codeforces или не согласуются с нормами общения здесь. То, что было вами опубликовано, является бессмысленным, безыдейным, мусорным, чрезмерно эмоциональным, агрессивным, оскорбительным, бессмысленным или нарушающим иные общепринятые этические нормы цивилизованного общения. Возможно, опубликованный контент нарушал иные правила Codeforces. Возможно, контент был написан не на английском (или на русском, если вы указали этот язык для записи в блоге или комментария). Пожалуйста, впредь будьте взвешены в ваших суждениях, аргументированы, вежливы, следуйте приличиям, не нарушайте правила сообщества. Используйте здравый смысл при анализе, чтобы писать или не писать какой-либо контент. Не следует публиковать юмористический контент, особенно если он не интересен широкой части аудитории, повторяет существующий или не имеет отношения к соревновательному программированию. Ваш аккаунт был переведен в режим read-only на 48 часов. Ваши последние комментарии, записи в блог, личные сообщения удалены. Надеемся, что вы сделаете выводы и подобная ситуация впредь не повторится. В случае повторения нарушений к вашему аккаунту могут быть применены более серьезные штрафные санкции вплоть до его блокировки.
      Ответить
        • Назвал non binary программиста "пидором очкастым"
          Ответить
          • > non binary программиста

            Тяжело программировать под Сетунь...
            Ответить
            • Кстати, а как портировать сишку под сетунь? sizeof будет работать?
              Ответить
              • sizeof то будет, он один хрен в попугаях, а вот что делать с битоёбством -- х.з.
                Ответить
                • в каких попугаях? int из четрех тритов и сайзов бдует 4?

                  Да, поведение бинарных операторов типа побитовово И и ИЛИ будет интересно
                  Ответить
                  • > четырёх

                    Фу! Отбрось бинарное мышление.

                    Пусть в char (трайте) будет 9 тритов. А sizeof(int) например 3 трайта будет.
                    Ответить
                    • А логика всё равно бинарная или например оператор "==" может вернуть 0,1 или 2?
                      Ответить
              • Вообще, зависит от того, зачем мы сишку туда портируем. Скорее всего, чтобы существующий код гонять. Иначе проще сделать новый язык и не париться.

                Тогда можно сделать совместимую с двоичной машиной сёмантику для and, or и xor -- двойки трактовать как единички. Старый код в принципе будет работать если обмазать его tri2bin и bin2tri вокруг битоёбств.

                А для троичной логики уже добавить новые операторы.
                Ответить
                • Хорошо, нахрен сишку. вот еще двоинчную логику на троичной эмулить

                  Давай придумаем высокоуровневый ЯП для Сетуни.
                  Как будет выглядеть сортировка пузырьком?
                  Ответить
                  • Ну числа как числа...

                    Разве что бул можно сделать с да/нет/х.з. как в sql.
                    Ответить

Добавить комментарий

Переведи на "PHP", guest!

    А не использовать ли нам bbcode?


    8