автор Анудж Пахаде

Эта публикация предполагает, что вы знаете, что такое китайская теорема остатка (CRT), и сосредоточена на ее реализации Java. Если вы этого не сделаете, я рекомендую вам прочитать здесь.

Ссылку на полный код можно найти в конце этой публикации. Итак начнем.

Что нам нужно отыскать?

Нам нужно найти X. ?

Заявление звучит так:

Существует а минимальное положительное число X такой, что:

X % number[0]    =  remainder[0], X % number[1]    =  remainder[1], ...............X % number[k-1]  =  remainder[k-1]

Итак, у нас есть два массива.

1. Массив чисел: Все числа в этом массиве попарно относительно просты. Это означает, что выберите любые два числа из массива, вы увидите, что их самый общий делитель равен 1.
2. Массив остатков: Как вы можете видеть в выражениях выше, когда X делится на число п от номер массива он оставляет соответствующий остаток от остаток массив.

Этапы внедрения ЭЛТ

Это шаги или, как мы, инженеры, говорят, «алгоритм» для реализации CRT.

Шаг 1: Найдите произведение всех чисел в первом массиве.

for(int i=0; i<number.length; i++ ){   product *= number[i];}

Шаг 2: Найдите частичное произведение каждого числа.

Частичное произведение п= продукт/п

for(int i=0; i<num.length; i++){   partialProduct[i] = product/number[i];}

3. Найдите модульный мультипликативный обратный к числу[i] по модулю частичного Продукта[i].

Здесь мы находим обратное с помощью расширенного алгоритма Евклида. Итак, звоним computeInverse(partialProduct[i],количество[i])

public static int computeInverse(int a, int b){         int m = b, t, q;         int x = 0, y = 1;               if (b == 1)             return 0;               // Apply extended Euclid Algorithm         while (a > 1)         {             // q is quotient             q = a / b;             t = b;                   // now proceed same as Euclid's algorithm             b = a % b;a = t;             t = x;             x = y - q * x;             y = t;         }               // Make x1 positive         if (y < 0)          y += m;               return y;     }

Шаг 4: Окончательная сумма

sum += partialProduct[i] * inverse[i] * rem[i];

Шаг 5: Поверните самый маленький X

Чтобы найти наименьшее из всех решений, мы делим сумму в шаге 4 на произведение в шаге 2.

return sum % product;

Таким образом, мы нашли свой X. Я рекомендовал бы попробовать реализовать код самостоятельно, прежде чем просматривать код по ссылке ниже.

Спасибо, что прочитали сообщение. Надеюсь, это помогло вам. Оставляйте предложения в комментариях ниже или свяжитесь со мной с лучшей версией этого кода или запросами на anujp5678[at]Gmail[dot]com или свяжитесь со мной на LinkedIn.

Пожалуйста, хлопайте. ? Плески мотивируют.

Веселой и счастливой кодировки! 🙂