Автор задачи: Даниил Голов, разработчик: Егор Юлин
Обозначим за $$$A = \max(a)$$$.
Немного переформулируем задачу. Запишем $$$a_i \bmod t$$$ как $$$a_i - \lfloor \frac{a_i}{t} \rfloor \cdot t$$$, и обозначим $$$\lfloor \frac{a_i}{t} \rfloor$$$ за $$$d_i$$$. Тогда для максимизации $$$\sum\limits_{i=1}^{n} (a_i \bmod t)$$$ нам нужно минимизировать $$$\sum\limits_{i=1}^{n} (d_i \cdot t) = t \cdot \sum\limits_{i=1}^{n} d_i$$$.
Посмотрим, как меняется $$$d_i$$$ при различных $$$t$$$.
Тогда для $$$t \le \sqrt{A}$$$ переберем $$$t$$$, и для каждого найдем ответ; это будет работать за $$$\mathcal{O}(n \sqrt{A})$$$.
Для всех остальных $$$t$$$ мы знаем, что $$$d_i$$$ принимает не более $$$\sqrt{A}$$$ различных значений; найдем отрезки, на которых оно принимает определенные значения. После чего будем обрабатывать различные $$$d_i$$$ при помощи сортировки событий, при этом будем обрабатывать все $$$d_i$$$ одновременно.
Так как каждое $$$d_i$$$ принимает не более $$$\sqrt{A}$$$ различных значений, то всего будет не более $$$n \sqrt{A}$$$ событий и время работы будет равно $$$O(n \sqrt{A})$$$. Интервал $$$t$$$, при котором $$$d_i$$$ неизменно и равно фиксированному числу, можно найти либо формулой, либо двоичным поиском. Решение через формулу гарантированно проходило по времени.
Итоговое время работы равно $$$\mathcal{O}(n \sqrt{A})$$$.