Будем решать задачу методов «разделяй и властвуй».
Разобьем число пополам, для младшей половины переберм цифры вместо вопросиков и посчитаем остатки при делении на m. Для старшей половины проделаем то же самое.
Теперь нужно выбрать остаток из старшей половины и из младшей, так чтобы минимизировать результирующий остаток. Пусть мы выбрали остаток из старшей половины, равынй a, из младшей — b, тогда результирующий остаток будет равен , где k — количество цифр в младшей половине числа.
Умножим все остатки из большей половины на 10k по модулю m. Теперь отсортируем остатки в обеих частях. Это можно сделать двумя способами: либо обычной сортировкой, либо используя подход с битовыми масками.
Первый способ не представляет сложности в реализации, но с ним могли возникнуть проблемы со временем исполнения, так как нам нужно отсортировать два массива по 107 элементов каждый. Скорость выполнения этой части решения очень зависит от используемого вами языка и компилятора.
Второй подход с битовыми масками представлял следующее: будем хранить в каждой ячейке массива 32-битную маску — какие числа присутствуют в данном массиве. То есть, если число x присутствует в массиве, то в элементе массива , в бите под номером
будет записана единица, иначе — ноль.
Тогда для меньшей части пометим в этом массиве остатки, которые имеются в левой части числа и просто пройдем по числам от 0 до 107 и проверим, что соотвествующий бит равен единице. Размер этого массива будет составлять , и сортировка произойдет за 107 операций.
Для большей части все немного сложнее, так как мы умножили все значения на 10k и взяли по модулю m и теперь все значения лежат в промежутке от 0 до m - 1. Заведем массив с битовыми масками, размером . Пометим в нем все числа из правой части. Теперь нужно получить их в отсортированном порядке. Просто пройтись от 0 до m будет затратно по времени, поэтому воспользуемся свойством, что массив разрежен, и среди 109 значений в нем могут быть только 107. Будем проходить только по тем маскам, значения которых неравны нулю. Таких масок будет не более 107, и суммарный проход по всех их битам займет не более
. Также возможны оптимизации, которые уменьшают это количество до
.
Вернемся теперь к решению. Пусть мы отсортировали остатки в меньшей и большей половинах, обозначим эти массивы за li и rj соотвественно. Теперь нужно выбрать из этих двух массивов такие остатки li и rj, что минимально. Это можно сделать двумя указателями, заметив тот факт, что для каждого li минимальный остаток могут давать только два значения r: r0 и такое rk, что li + rk ≥ m, и li + rk - 1 < m. Это следует из того, что для любых i, j: li + rj < 2 × m. То есть просто увеличиваем указатель i, и для каждого i уменьшаем k, пока не встретим первое такое rk - 1, что li + rk - 1 < m.
Выбрав минимум из всех таких пар мы получим ответ.
Сложность данного решения либо: либо
в зависимости от реализации.