Ответы пользователя по тегу Алгоритмы
  • Функцию, похожую на хэш, с коротким непоследовательным дайджестом и без коллизий?

    @MikeMirzayanov
    Можно так. Работает для всех m от 1 до MOD-1. Если не хватает, то можно либо увеличить константы (тогда может вырасти длина), либо чуток адаптировать алгоритм. Я подогнал, чтобы было как в примере 6 знаков в коде. На самом деле можно все делать в 64-битных переменных, просто так на Java удобнее.

        private static final BigInteger MULTIPLIER = BigInteger.valueOf(13L);
        private static final BigInteger MOD = BigInteger.valueOf(99990001L);
        private static final BigInteger ADDEND = BigInteger.valueOf(699930007L);
    
        public static String encode(long m) {
            if (m <= 0 || m >= MOD.longValue()) {
                throw new IllegalArgumentException("Argument is out of range.");
            }
            return BigInteger.valueOf(m).modInverse(MOD).multiply(MULTIPLIER)
                    .add(ADDEND).toString(36).toUpperCase();
        }
    
        public static long decode(String encoded) {
            return new BigInteger(encoded.toLowerCase(), 36).subtract(ADDEND).divide(MULTIPLIER)
                    .modInverse(MOD).longValue();
        }
    


    Вот примеры того, что получается (для разных m):

    1 BKPXGK
    2 MBOAIK
    3 PWNQV8
    4 RP5H1K
    5 SRUICK
    10000 X2JV9T
    10001 PWMTFN
    10002 U025II
    10003 TRK6AU
    10004 JRJEMK
    10005 UARMRU
    10006 S2NCNJ
    10007 R1E1UK
    10008 HRCMBX
    10009 WU4GN7
    99989996 FVI2O7
    99989997 GY73Z7
    99989998 IQOU5J
    99989999 MBOAI7
    99990000 X2MNK7
    
    Ответ написан
    Комментировать
  • Интерестная задачка, спортивное программирование, разобраться?

    @MikeMirzayanov
    Если тесты делали не с любовью, то пройдет такой вариант. Можно сравнивать столбцы по суммам логарифмов чисел в них. Надо быть аккуратным с отрицательными числами и нулем, но это детали. Вычисления лучше делать в long double (для C/C++). Вероятно, если подумать, то окажется что это предполагаемое решение.
    Ответ написан
    2 комментария