\(\min\{(ax + b) \bmod m : 0 \leq x \leq n\}\) を求めよ。(library checker)
\(a\cdot0+b\)、または\(ax+b=mq+r\)と表したときに\(0 \leq r < a\)となるものがminの候補。商qは\(1 \leq q \leq \lfloor \frac{an+b}{m} \rfloor\)の範囲を取るので、 \begin{align} &\min\{(ax + b) \bmod m : 0 \leq x \leq n\}\\ =&\min(\{(b - mq) \bmod a : 1\leq q \leq \lfloor \frac{an+b}{m} \rfloor\}\cup \{b\}) \end{align} \(q\)を\(q_0-q\)に変数変換することで\(-m \bmod a\)を\(m \bmod a\)にできるので、O(log m)。 \(a,m\)が与えられるので、\(a^x=x \bmod m\)を満たすxを求めよ。 degwer
原始根

nyaan