Если существует C, взаимно простой с M, то существует такой x, что Cx = M - 1 (mod M); установите все остальные x в 0 и установите значение, соответствующее нашему специальному C, на требуемое значение. Вы не можете сделать лучше, чем М - 1 (мод М).
В противном случае, если есть два взаимных числа C, скажем, C1 и C2, то можно получить любую сумму, превышающую (C1 - 1) (C2 - 1) - 1 (посмотрите на проблему с монетой или число Фробениуса ); поскольку должно существовать некоторое число, большее, чем это конгруэнтное М - 1 (мод М), это так хорошо, как вы можете сделать; установите все остальные x равными 0 и найдите x1, x2, необходимые для получения M - 1.
В противном случае, найдите минимальный наибольший общий делитель, сравнив сначала все C с M напрямую, а затем все C с друг другом. Пусть этот минимальный наибольший общий знаменатель будет называться m. Затем можно добраться до M - m (mod M), используя вышеуказанные методы с модификацией. Тем не менее, невозможно получить значение M - 1 или что-либо выше, чем M - m (mod M), поскольку все числа имеют общий множитель.
Чтобы на самом деле найти числа в этих случаях, я бы подумал сначала определить случай; затем, следуя стратегии (1 или 2 ненулевых члена), просто перебирайте возможности. Поскольку мы сократили его до одного-двух терминов, это не страшно. Возможно, есть более разумный способ сделать это ... если требуется что-то более сложное, чем проверка возможностей, пожалуйста, прокомментируйте, и я еще раз вернусь к этому.
UPDATE
В комментариях высказывалось предположение, что обработка третьего случая - без взаимно простых коэффициентов - была неправильной и неправильной. Рассмотрим случай C1 = 14, C2 = 21, M = 6. Метод, описанный выше, находит минимальный попарно GCD равным 2 и говорит, что максимально достижимый составляет 6 - 2 = 4; тем не менее, вы можете получить 5 (mod M) просто, взяв x1 = 1 и x2 = 1. Возможно, что действительно нужно сделать, чтобы получить правильный ответ, это рассмотреть все попарные GCD и применить те же рассуждения к ним. То есть наши попарные GCD равны 2, 3 и 7. Благодаря решению задачи о монетах для n = 2 это означает, что, комбинируя каждую пару, мы можем получить любое число, достаточно большое кратное этим GCD. Это означает, что по модулю M сами GCD достижимы; таким образом, мы можем рекурсивно применить вышеупомянутое решение к парным GCD, пока ВСЕ парные GCD не будут иметь общий термин (тогда мой оригинальный анализ случая будет правильным); ИЛИ, один из попарных GCD становится равным 1, и в этом случае ответом является M - 1.
Обратите внимание, что, вероятно, можно отслеживать рекурсию и случаи по пути, чтобы восстановить правильный ответ в терминах исходного Cs. Оставлено как упражнение.
UPDATE:
Основываясь на комментариях, я сейчас попытаюсь применить этот (исправленный?) Метод к реальному примеру.
M, C1, C2 = 385, 42, 30
GCD(M, C1) = 7
GCD(M, C2) = 5
GCD(C1, C2) = 6
7 and 5 are coprime so we can get any number greater than (7-1)(5-1)-1
any number greater than 23 is obtainable
384 = 2*[7] + 74*[5]
7 is obtainable
7 = 46*[42]
5 is obtainable
5 = 13*[30]
combining, we get
384 = 2*[7] + 74*[5]
= 2*46*[42] + 74*13*[30]
= 92*[42] + 962[30]
~ 92*C1 + 192C2