ModSum

Sums of mod'ed arithmetic progressions. modsum(to, c, k, m) = Σ_i=0^to-1(ki+c) % m. divsum is similar but for floored division.

Time: log(m), with a large constant. 16 lines Tested for all |k|,|c|,to,m <= 50, and on kattis:aladin

content/number-theory/ModSum.h — Simon Lindholm, source: own work

typedef unsigned long long ull;
ull sumsq(ull to) { return to / 2 * ((to-1) | 1); }

ull divsum(ull to, ull c, ull k, ull m) {
	ull res = k / m * sumsq(to) + c / m * to;
	k %= m; c %= m;
	if (!k) return res;
	ull to2 = (to * k + c) / m;
	return res + (to - 1) * to2 - divsum(to2, m-1 - c, m, k);
}

ll modsum(ull to, ll c, ll k, ll m) {
	c = ((c % m) + m) % m;
	k = ((k % m) + m) % m;
	return to * c + k * sumsq(to) - m * divsum(to, c, k, m);
}