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:

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.

Due to the way we set $$$a$$$ and $$$M$$$ at every step, we do at most $$$\mathcal{O}(\log M)$$$ steps, and every step takes $$$\mathcal{O}(1)$$$ time.

#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); }

// 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) {
		na = posMod(-m, a);
		nb = (b < a ? b : posMod(b - m, a));
		nm = a;
		if (mSub(nb, b0, m0) * ia0 % 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.

EDIT: turns out the other case handled in my original solution was pointless >_>. I removed it, much simplifying the explanation and code :)