Contact Form Submission - Suggestion (Solution: Kilonova - Sum of divisors)

[maggieliu05]

Someone submitted the contact form!

URL: https://usaco.guide/problems/kilonova-sumdiv/solution
Module: Solution: Kilonova - Sum of divisors
Topic: Suggestion
Message:
It would be good to give a solution that doesn't require modular inverse and works for arbitrary moduli.

[bqi343]

Example (without template):

pair<mi, mi> operator*(pair<mi, mi> l, pair<mi, mi> r) {
	return {l.f * r.f, l.s + l.f * r.s};
}

pair<mi, mi> geo_seq(mi p, ll e) {
	// returns: {p^e, sum_{i=0}^{e-1}p^i}
	if (e == 0) return {1, 0};
	if (e & 1) return geo_seq(p, e - 1) * pair<mi, mi>{p, 1};
	auto half = geo_seq(p, e / 2);
	return half * half;
}

int main() {
	setIO("sumdiv");
	def(ll, A, B);
	V<pair<ll, int>> v = factor(A);
	mi ans = 1;
	for (auto [p, e] : v) {
		auto [pe, sum_pe] = geo_seq(p, e);
		auto [_, sum_ofac] = geo_seq(pe, B);
		ans *= p * sum_pe * sum_ofac + 1;
	}
	ps(ans);
}

[lamaqdahodwala]

I pasted the alternate implementation alongside the pre-existing solution in PR #5431