Fast modulo (via Barrett reduction, works for arbitrary 64-bit integers except d = 1)

barrett.cpp

typedef long long ll;
typedef unsigned long long ull;
typedef __uint128_t L;

struct Barrett {
	ull d, m;
	Barrett(ull d) : d(d), m(ull((L(1) << 64) / d)) {}

	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * d;
		if (r >= d) r -= d;
		return r;
	}
};