概要
$O(\log M)$ 時間で解く方法を解説します。
準備：最良近似分数と Farey 数列
この記事において、「有理数 $\frac{p}{q}$」などと書けば、$p,q$ は互いに素な整数かつ $q\geq 1$ であるものとします。
次の定義をします。
$x$ を実数とする。$x$ 以下の有理数 $\frac{p}{q}$ が $x$ の下側最良近似分数であるとは、$1\leq q’ \leq q$ かつ $\frac{p}{q} < \frac{p’}{q’} \leq x$ となる有理数 $\frac{p’}{q’}$ が存在しないことをいう。上側最良近似分数も同様に定義する。
「最良近似分数」という用語はある程度一般的だと思いますが、「上側」「下側」の区別をしているのはこの記事での独自の用語かもしれません。
Farey 数列 の性質より、これらは次の手順で計算していくことができます。ある大きさの分母までを考えた $x$ の下側・上側最良近似分数 $p/q$, $r/s$ を次の手順で計算していきます。まず分母が $1$ の最良近似分数でこれらを初期化しておきます。そのあと、次のようにして「次の」最良近似分数を求めていきます。
- $x = (p+r) / (q+s)$ となったら、その分数が次の上側・下側最良近似分数である。計算を終了する。
- そうでない場合、$(p+r) / (q+s)$ が $x$ より小さい・大きいのいずれであるかによって、この分数を下側・上側の最良近似分数として更新する
なお、この過程を木構造で表すと Stern-Brocot 木が導出されます。
$x$ の下側・上側の最良近似分数のうち分母が $m$ 以下のものは、最悪の場合で $\Omega(m)$ 個存在しますが、同じ側の最良近似分数が連続して更新される部分をまとめると、上のアルゴリズムは $O(\log m)$ ステップになります。
（なお、「同じ側の最良近似分数を得ることを可能な限り繰り返す」操作のみを取り出すことで、連分数展開による近似分数の計算が導出されます。また、Stern-Brocot 木の言葉では、根から分母が $m$ の分数までのパスの連長圧縮の長さが $O(\log m)$ ということができます）
なお、この計算過程で有理数 $p/q$ と $x$ の大小比較を何度も行うことになりますが、$p/q-x$ ではなく $p-qx$ に注目すると計算が簡潔になりやすいです（$(p+r)/(q+s)$ に対するそれが $p/q, r/s$ の場合の和として計算できるため）。
具体例の観察
$a = 71$, $b = 85$, $m = 100$ として、$f(x) = (ax + b) \bmod m = (71x + 85) \bmod 100$ とします。この関数のグラフは次のようになります。
橙色でプロットしている点は、prefix minimum を与える点、つまり $f(x) = \min\{f(0), \ldots, f(x)\}$ を満たす点です。prefix minimum を与える点全体がどのようなものかが求まれば本問題を解くことができます。
この例の場合、具体的な座標は次の通りです：
$$(0,85), \quad (1,56), \quad (2,27),\quad (6,11),\quad (13,8),\quad (20,5),\quad (27,2),\quad (65,0).$$
これらは $4$ つの等差数列に分解することができます：
- $x=0, 1, 2$
- $x = 2, 6$
- $x = 6,13,20,27$
- $x = 27,65$
以下では一般に、prefix minimum を与える点全体が $O(\log m)$ 個の等差数列に分解できることと、その計算方法を確認します。
次の prefix minimum の計算
$(X,Y)$ が prefix minimum を与える点かつ $Y>0$ であるとして、次の prefix minimum を求める問題を考えます。
都合により $-a$ を改めて $a$ と書くことにします。したがって $f(x) = (-ax+b) \bmod m$ です。$f(X) = Y$ のとき、$f(X+q) = (Y-aq) \bmod m$ です。よって、これは次の問題に帰着できます：
$a, m, Y$ が与えられる。$(aq \bmod m) \leq Y$ となる正整数 $q$ の最小値を求めよ。
$q$ をこの問題の解とします。$p = \lfloor aq / m\rfloor$ とします。したがって、$0\leqq aq-mp \leqq Y$ となります。特に $\frac{p}{q} \leq \frac{a}{m}$ が成り立ちます。ここで、次が成り立ちます：
$\frac{p}{q}$ は $\frac{a}{m}$ の下側最良近似分数である。
証明しましょう。$1\leq q’ \leq q$ かつ $\frac{p}{q} < \frac{p’}{q’}\leq \frac{a}{m}$ であるとします。このとき $0\leq (a/m)-(p’/q’) < (a/m)-(p/q)$ なので、$1\leq q’ \leq q$ と合わせて $0\leq mq'((a/m)-(p’/q’)) < mq((a/m)-(p’/q’))$ が分かります。よって $0\leq aq’-mp’ < aq-mp \leq Y$ より $(aq’ \bmod m) \leq Y$ となります。$q$ の最小性より $q=q’$ ということになりますが、このとき $\frac{p+1}{q}\leq \frac{a}{m}$ となり $p =\lfloor aq / m\rfloor$ に矛盾します。
さて、ここまでの理解に基づいて、prefix minimum をすべて求めることが可能です。
$(X,Y)$ まで計算したとします。$a/m$ の下側最良近似分数 $p/q$ のうちではじめて $c = aq-mp \leq Y$ を満たすものを求めます。$k = \lfloor Y / c \rfloor$ とするとき、等差数列をなす $k$ 個の prefix minimum $(X + qi, Y-ci)$ ($1\leq i\leq k$) が得られます。$(X, Y)$ を $(X + qk, Y-ck)$ に置き換えて、この計算を繰りかえします。$a/m = p/q$（したがって $c=0$）となったら終了します。
上記のステップを $1$ ステップとすると、$1$ ステップあたり $Y$ の大きさが $1/2$ 倍以下になるので、$O(\log m)$ ステップで $a/m=p/q$ に至り終了します。
各ステップでは下側最良近似分数の探索が必要です。これを分母が $1$ の最良近似分数から順に探索すると、ステップごとに $O(\log m)$ 時間かかってしまいます。しかし、探索すべき最良近似分数の分母の大きさは単調増加なので、$1$ から探索しなおすのではなく前回探索したところから探索を再開する形にすれば、最良近似分数の計算も全体で $O(\log m)$ 時間となります。
