I saw a blog (thanks to oversolver for finding it!) earlier today asking how to solve the following problem:

Given a linear function $$$ax + b$$$, find the minimum $$$x \geq 0$$$ such that $$$ax + b \in [L, R]\ (\text{mod } M)$$$.

To solve that problem, we can make the following reduction: If $$$gcd(a, M) > 1$$$, we divide everything by the GCD. The $$$x$$$ for which $$$ax + b = L\ (\text{mod } M)$$$ is $$$(L - b) a^{-1}\ (\text{mod } M)$$$. Denote this value by $$$b_0$$$. Then, the minimum $$$x$$$ to get to $$$L + y$$$ is $$$a^{-1} y + b_0\ (\text{mod } M)$$$. This gives us a reduced problem:

Find the minimum value of $$$ay + b \text{ mod } M$$$ over $$$y \leq k$$$.

This seemed pretty hard, but surprisingly I figured out how to do it in $$$\mathcal{O}(\log M)$$$ time! The algorithm is as follows:

In every step, we reduce the modulo from $$$M$$$ to $$$\min(a, M - a) \leq M / 2$$$. This guarantees we do at most $$$\mathcal{O}(\log M)$$$ steps.

To reduce it to $$$a$$$, we consider the first value $$$s$$$ among $$$[0, a)$$$ achieved by $$$ay + b$$$. If $$$b < a$$$, it is $$$b$$$. Otherwise, it is $$$b - M\text{ mod } a$$$. We check in $$$\mathcal{O}(1)$$$ if we reach $$$s$$$ for some $$$y \leq k$$$. If we do, set $$$M$$$ to $$$a$$$, $$$a$$$ to $$$-M \text{ mod } a$$$ and $$$b$$$ to $$$s$$$. Otherwise, output $$$b$$$ as the first $$$a$$$ values are the only values such that the previous value was larger, thus if we never attain them, the first value we attain is the largest we do.

To reduce it to $$$M - a$$$, we consider the first value $$$s = b \text{ mod } M - a$$$ among $$$[0, M - a)$$$ achieved by $$$ay + b$$$. If we reach $$$s$$$ for some $$$y \leq k$$$, set $$$M$$$ to $$$M - a$$$, $$$a$$$ to $$$a \text{ mod } M - a$$$ and $$$b$$$ to $$$s$$$. Otherwise, we can calculate the number of steps to go from $$$v$$$ to $$$v - (M - a)$$$ for $$$v \geq M - a$$$, and from this the smallest value we can reach with $$$y \leq k$$$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<ll, ll> extEucMod(ll a, ll b, ll p) {
	if (b == 0) return {1, 0};
	ll m = a / b;
	auto sub = extEucMod(b, a - b * m, p);
	return {sub.second, (sub.first - m*sub.second) % p};
}
ll modInv(ll a, ll p) {
	ll res = extEucMod(p, a, p).second;
	return (res < 0 ? res + p : res);
}
ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
ll mSub(ll a, ll b, ll m) { return (a >= b ? a - b : a - b + m); }
ll posMod(ll a, ll m) { ll res = a % m; return (res < 0 ? res + m : res); }
ll getSteps(ll t, ll ia, ll b, ll m) { return mSub(t, b, m) * ia % m; }

// Returns minimum value of ax + b (mod m) for x \in [0, k]. O(log m) time
ll minRem(ll a, ll b, ll m, ll k) {
	for (ll g = gcd(a, m); g > 1;) return g * minRem(a/g, b/g, m/g, k) + (b % g);
	for (ll b0 = b, m0 = m, ia0 = modInv(a, m), na, nb, nm; a; a = na, b = nb, m = nm) {
		if (a > m - a) {
			na = a % (m - a);
			nb = b % (m - a);
			nm = m - a;
			for (ll steps = getSteps(nb, ia0, b0, m0); steps > k;) {
				ll add = steps - getSteps(nb + nm, ia0, b0, m0);
				return nb + nm * ((steps - k + (add - 1)) / add);
			}
		} else {
			na = posMod(-m, a);
			nb = (b < a ? b : posMod(b - m, a));
			nm = a;
			if (getSteps(nb, ia0, b0, m0) > k) break;
		}
	}
	return b;
}

// Returns minimum x such that ax + b (mod m) \in [le, ri] or -1 if there is no such x. O(log m) time
ll firstInRange(ll a, ll b, ll m, ll le, ll ri) {
	for (ll g = gcd(a, m); g > 1;) return firstInRange(a/g, b/g, m/g, le/g + (le % g > b % g), ri/g - (ri % g < b % g));
	if (le > ri) return -1; // impossible
	ll ia = modInv(a, m);
	return minRem(ia, mSub(le, b, m) * ia % m, m, ri - le);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll a, b, m, le, ri;
	cin >> a >> b >> m >> le >> ri;
	cout << firstInRange(a, b, m, le, ri) << '\n';
}

What I wanted to ask is, is this a known problem, and is there a simpler or perhaps even faster solution to it? The problem seems fairly simple, so I doubt nobody has thought about it before.