Counting elements less than $k$ in arithmetic progressions modulo $m$ Given $a_1$, $b$, $n$ and $m$, which define an arithmetic progression $a$ as follows:
$$
a_{i+1}=(a_i+b)\bmod m
$$
for $1 \leq i < n$ (the arithmetic progression has $n$ elements).
Is there some algorithm to quickly determine how many elements of $a$ are less than $k$?
If $n$ is small, we can use the straightforward $O(n)$ algorithm, just compute all elements and count how many are less than $k$.
If $m$ is small, we can use a slightly more sophisticated $O(m)$ algorithm, by noticing that this sequence is periodic with a period of at most $m$, and hence doing some cycle-detection.
But what if $n$ and $m$ can both be large? Is there a well-known algorithm that can solve this problem in general?
 A: Call $g$ the greatest common divisor of $b$ and $m$. 
If $n$ is large ($n\geq \frac{m}{g}$) then the set of elements in your sequence is the set $$\left\lbrace a_1+\ell g\ \left|\  \ell=0\ldots \frac{m}{g}-1\right\rbrace\right.$$
We are using the fact that the subgroup $\left< b\right>\subset \Bbb Z_m$ is generated by its smallest element $g$ and has order $\frac{m}{g}$.
It doesn't make a huge difference what $a_1$ exactly is: the number of elements in $a$ that are less than $k$ is either $$\left\lceil\frac k{g}\right\rceil$$ or $$\left\lfloor\frac k{g}\right\rfloor$$

As you can see on this picture the first case occurs when the smallest element in $a$ is close enough to $0$: if it gets too close to $g$, you lose a pink dot to the other side of $k$. 
More precisely the first case occurs when $a_{\min}\in \left[0, k-g\left\lfloor\frac k{g}\right\rfloor\right]$. But $a_\min$ is also the distance between any element of the sequence $a$ and its nearest multiple of $g$ on the left. Therefore the condition becomes:
$$a_1-g\left\lfloor\frac {a_1}{g}\right\rfloor\in \left[0, k-g\left\lfloor\frac k{g}\right\rfloor\right]$$
Under that condition $\sharp a$ is $\left\lceil\frac k{g}\right\rceil$, and it is $\left\lfloor\frac k{g}\right\rfloor$ otherwise.
