Dmitry81923, Вряд ли есть сайты. Но не надо самому писать. Там по ссылке даже код есть с объяснением.
Но вообще, если оно вам не понятно, то можно проще. Вам же всего один раз обратные найти, можно сделать более медленным методом. Для каждого множителя A просто переберите все числа X от 0 до 65535 в цикле. Найдите то единственное, при котором A*X == 1:
uint16_t a = 26399;
uint16_t x = 0;
while(true) {
uint16_t t = a;
t *= x;
if (t == 1) {
cout << x << "\n";
break;
}
++x;
};
Dmitry81923, Вот, допустим, мы работаем с вещественными числами. Чтобы отменить умножение на 2 надо поделить на 2. Но как вообще определить деление? Математики определили его как домножение на обратное - на 0.5. 2*0.5=1. Точно так же 5*0.2 = 1 и поэтому для отмены умножения на 5 надо домножить на 0.2. А для отмены умножения на 3 надо домножить на 0.3333... Пока понятно?
Это было среди вещественных чисел. Но у вас-то в программе операции среди целых чисел помодулю 65536. Потому что state 16-битный и переполнение просто обрезает старшие биты. Те же самые числа можно получать, если перемножать в 32-битные и брать остаток от деления на 65536 (на самом деле процессор скорее всего так и работает).
Обратите внимание, в группе по модулю сложение и умножение работают похоже на обычные числа. Но вот деление - совсем нет. Потому что тупо не все числа можно делить по обычным школьным правилам. Вот как поделить 3 на 27569 и получить целое число в 16 бит? По школьным правилам оно тупо не делится. А из математики груп получается, что операция должна быть применима ко всем членам группы. Надо придумать такое "деление", что бы любое число от 0 до 65535 можно было "поделить".
Так вот, вам надо почитать про группы, операции по модулю и потом ссылку в ответе про "обратные по модулю".
И вот так получается, что у некоторых чисел есть обратные по модулю. 26399*27569 = 1 (mod 65536). Напишите программу, которая эти два числа перемножит в 16-битных. Получите 1. Точно так же, как 2*0.5 = 1 среди вещественных чисел, по модулю 65536 эти два числа обратны к друг другу.
Поэтому можно домножить на обратное, чтобы отменить домножение:
(x*26399)*27569 = x*(26399*27569) = x*1 = x (mod 65536).
Найти эти обратные можно, например, с помощью расширенного алгоритма эвклида.
Обратимы все множители, взаимнопростые (не имеющие общих делителей) с модулем. В вашем случае - нечетные, потому что модуль - степень двойки.
Maxim Siomin, Совремменные процессоры могут выполнять несколько сот миллионов операций в секунду. Допустим, мобильный процессор - слабенький. Пусть будет 100 000 000 операций в секунду. у вас будет 3 разности, 3 произведения, два сравнения на каждый цвет. ну еще по мелочи округлим до 20 операций на цвет. Итого - 30000 операций на каждый запрос. Итого - в секунду поместяца 3300 запроса. А вам надо упихнуть 120. Т.е. все помещается и еще 97% свободного процессорного времени остается.
Maxim Siomin, Нет, это вопрос не про платформу или можность процессора, а про количество цветов и скорость поступления запросов. Т.е. если у вас сотни тысяч цветов задано и пользователю надо искать ближайший несколько раз в секунду - то тут да, скорость важна. Если же у вас всего 20-50 цветов и запрос будет выполнятся максимум раз в секунду, то тут подойдет и простой линейный алгоритм.
Dmitry81923, Позвольте прокоментировать. Ваш код очень плох. Никогда не надо работать с адресами через int64_t. Это непереносимо, разные версии компиляторов и уровни оптимизации могут вам все сломать.
Погуглите про "арифметику указателей" в C. К char* можно прямо прибавлять 1, не надо его для этого приводить к int64_t.
Далее, ваш метод прочитать 2 байта из arg1 - вот так вот просто читая unsigned int по какому-то адресу - это тоже неправильно. Или делайте memcpy, или вручную через сдвиги и битовые операции:
unsigned int b1 = *text++;
unsigned int b2 = *text++;
state = (b1 << 8) | b2;
То, что ваш код компилируется и работает на вашей машине вот сейчас - не гарантирует, что он сработает где-то еще. Может там версия компилятора другая, или настройки другие (уровень оптимизации особенно).
Ну и далее, названия arg1, arg3 - это очень и очень плохо. Вы там сами не путаетесь? Я понимаю в условиях соревнования, когда код надо писать быстрее называть переменные text, t, n, i, a. Это тоже не очень хорошо, но хоть устаявшиеся нормы есть (a - массив входных чисел, t - текст, n - количество входных чисел, i, j - индексы).
MaxKozlov, если он signed, то там undefined behavior при перепрлнении. А так, важно, что множители взаимнопросты с модулем (65536). Обратимо было бы даже если бы они не были простыми, а просто нечетными.
Dmitry81923, Прочитали мой ответ? Прочитали ссылку на обратне по модулю?
Понимаете, что значит "по модулю"?
Вы, вроде, понимаете, что вам надо обратить операции. Если в шифраторе стоит +65530, то в дешифраторе будет -65530, что то же самое, что +6 (потому что по модулю же все). Т.е. чтобы обратить прибавление 65530 вам надо прибавить обратное относилельно сложения.
Чтобы обратить умножение - вам надо домножить на обратное относительно умножения. Что бы найти конкретные множители вам надо пройтись по ссылке, написать расширенный алгоритм эвклида, и скормить ему все множители из вашего шифратора. Выданные алгоритмом числа и надо использовать в качестве множителей в дешифраторе.
Dmitry81923, Потому что деление нацело не является обратной операцией по модулю. Обратной операцией является домножение на обратное по модулю (это самое обратное можно найти расширенным алгоритмом евклида).
Dmitry81923, Вроде как джомножение идет только на нечетные числа. А значит там все обратимо. Перепроверьте ваш код, результаты для разных чисел не должны повторяться.
Вряд ли есть нейросети для этого. Видел какие-то научные статьи, где по куче фотографий помещения с разных точек восстанавливают 3d карту помещенния. Там, всякое машинное зрение выделяло фичи в картинках а потом вычислительная геометрия и линейная алгебра позволяли восстанавливать координаты. По видео это тем более возможно, если камера двигается.
Вадим Ушаков, Самый надежный и простой способ - скопировать исходники библиотеки, изменить как вам надо и вообще никак не включать в ваш проект саму библиотеку. Только измененную копию. При этом обновлять версию библиотеки надо вручную - пытаясь накатить туда ваши изменения и смотреть, что ничего не сломалось.
Еще вариант, это иметь две версии библиотеки, названные по-разному, собранные в dll. И тогда вы руками будете подгружать нужные вам функции из измененной библиотеки.
Вадим Ушаков, Максимум, что вам может дать автоматизация - это переименование функции сразу во всех файлах проекта. И то не факт, что вам это подойдет, если у вас там копии откуда-то взялись.
Когда появится инструмент способный исправлять вот эту вашу ошибку в коде, вам уже не надо будет копаться в С++ - нас всех заменят роботы.
Вадим Ушаков, Нарушить One Definition Rule не получится. Никак. Как не получится, например, писать конструкции языка на русском языке. Ну вот так компилятор устроен, что ему надо писать "for" а не "цикл". Точно также надо чтобы все функции в исполняемом файле имели разные сигнатуры.
Нужно или переименовать одну копию, или убрать лишние из проекта. Возможно надо будет вынести их в отдельную библиотеку, или отключать копии через директивы препроцессора.
Откуда у вас взялось желание использовать одинаково названные функции? Зачем? Почему? Если они идентичные по коду, то зачем вам копии? Если они разные, то как вы решаете, какая из них вызывается в каждом конкретном месте?
Антон Жучков, Вот как раз хотел спросить, а что делать в случае "abcd" и "cdba" - тут есть 2 варианта взять наибольшее LCS размером в 2, но оно или в первой строке раньше, или во второй. Значит у вас надо именно минимизировать вхождение в первой строке.
Антон Жучков, Наверно, что-то не так в вашем внешнем алгоритме. А что если самая длинная последовательность на конце? А последовательность на 1 короче - в самом начале?
Давайте вашу всю задачу, возможно тут надо не LCS вообще.
Если все же вам нужна первая LCS, то надо просто чуть-чуть модифицировать ваш алгоритм. Там, наверняка, где-то в цикле ищется максимальное число и вот там надо знаки правильно посавить (переписывать только если текущее значение строго больше пока найденого максимума).
Но вообще, если оно вам не понятно, то можно проще. Вам же всего один раз обратные найти, можно сделать более медленным методом. Для каждого множителя A просто переберите все числа X от 0 до 65535 в цикле. Найдите то единственное, при котором A*X == 1: