Правильно понимаю, что модуль находится под суммой?

Гер, скачай разбор отсюда. Задача aladin.

O(n), где n — размер модуля. Или это тоже имелось ввиду под линией?

Вот в этой статье в разделе 3 эта сумма считается за .

Получается x*b+a*((x*(x-1)/2) (mod n). Но это слишком просто, чтобы писать пост; что я понял не так? :) upd: упс, надо было читать комментарии перед написанием своего.

На онсайте Opencup'а летом 2011 года была задача — посчитать количество целых точек в прямоугольном треугольнике. И решалась она за . Эта задача достаточно просто к ней сводится. Алгоритм решения примерно тот же самый, что и алгоритм из статьи из комментария выше.

Коротко, и по русски ^_^
Научимся решать задачу для случая, когда a>=b.
Есть такое k, что a=k*b+c, где c<b.
Ответ, следовательно — [(k*b+c)/b]+[2(k*b+c)/b]+[3(k*b+c)/b]...+[n(k*b+c)/b].
Где [x] — то же самое, что и trunc(x).
На самом деле ответ состоит из двух частей — k+2k+3k+4k...+nk — это легко посчитать и [c/b]+[2c/b]+[3c/b]...+[nc/b] — это та же задача, только уже с новыми a,b,n.
Чтобы ее решить, просто как-бы мысленно повернем треугольник на 90 градусов и мы получим новые a,b,n для этого повернутого прямоугольника, хотя все равно понятно, что это будет одно и то же.
И эти a,b,n можно получить такими, чтобы выполнялось a>=b и опять решить задачу, которую мы научились решать.
И там еще надо будет немного повозиться с точками лежащими на гипотенузе.
На самом деле, все будет изменяться так же, как и в алгоритме Евклида. Так что мы получим решение за сложность, за которую работает Евклид, то есть за быстро.
Это примерные намеки на решение.
Мой код — решение задачи SPOJ GPINTRI.