В основном нам нужно выяснить, существует ли целое число k такое, что для всех i,
k mod l[i] = d[i],
и дано, что сумма l[i] равна n. Из теории чисел мы знаем, что если l[i] = f * g, f и g относительно простые, то уравнение
k mod l[i] = d[i]
эквивалентно уравнению
k mod f = d[i] mod f
k mod g = d[i] mod g.
Наша цель состоит в том, чтобы разложить d[i] в простые степени и проверить, что система уравнений разрешима для каждой простой степени.
Чтобы учесть l[i] по времени O(n), мы можем просто использовать пробное деление, так как время выполнения будет порядка
sum_i √l[i] ≤ sum_i l[i] = n.
Единственная другая часть объединяет два уравнения
k mod p^e = r
k mod p^f = s
для некоторой переменной k и заданного простого p, показателей e ≥ f и остатков r и s. С p^f|p^e это легко. Мы просто проверяем, что r mod p^f = s (для согласованности), а затем второе уравнение является избыточным. Если мы достигнем одного простого уравнения степени без раскрытия несогласованности, то система разрешима относительно этой основной степени.