クイズです。$p/q \equiv 714236805 \pmod{998244353}$ を満たす互いに素な整数のペア $(p, q)$ はなんでしょうか。
答えは $(113, 355)$ です*1。今日の話は、これを一般的に求める方法です。
裏話
$1/3 \equiv 332748118$ みたいなのだとパターンマッチで答えられてしまいそうな気がしたので、適当に難しそうな分数が欲しくなりました。 適当な分数と言えば、$1/\pi \approx 113/355$ だな〜と思って求めてみたところ、$876543210$ のアナグラムになっていてびっくりしました。
（追記）ねむかったので $\pi$ の近似分数の分子と分母を間違えていました。
競プロ用途に関して
「$998244353$ を法として求めた値が $598946612$ になったけどこれはなに？」「サンプルの答えが $713031681$ らしいけどこれはなに？」というのは比較的頻出シチュエーションかと思います。（非常に大きくなるので系ではなく、有理数で表せるので系の問題であれば）これらを有理数の形式で読みたいと思うことはよくあるでしょう*2。
しかし、分母や分子が大きくなることを許してしまうと、$714236805/1 \equiv 714236805 \pmod{998244353}$ や $3/220850530 \equiv 714236805 \pmod{998244353}$ のようなうれしくない分数を作れてしまいます。 そこで、分母と分子が適当なパラメータ未満であるような分数の表現を探すことにします。
ところで Chrome 拡張もあるみたいです。
これのソースコードをgitに上げました．よければ使ってみてください👍https://t.co/pgQdJUXsqQ https://t.co/aLUoIY4Qw0
— かつっぱ@ 競プロYouTuber (@catupper) 2020年12月4日
問題設定
$0\lt x\lt m$ および $n$, $d$ が与えられる。互いに素な整数の組 $(p, q)$ であって $p\equiv qx \pmod{m}$ を満たすものを求めよ。ただし、$|p| \lt n$ かつ $0\lt q\lt d$ とする。存在しない場合はその旨を報告せよ。
こんな感じになるでしょうか。後で示しますが $m \ge 2nd$ であれば解が一意になるので、分母の制限 $d$ のみを与えて、$m/2d \ge n$ を満たす $n$ の最大値 $n = \floor{m/2d}$ を暗に与えるものとしてもよいでしょう。あるいは、$n=d=\sqrt{m/2}$ とするのもよいでしょう。
たとえば後者の設定であれば、$x \lt \sqrt{m/2}$ の場合は自明解 $(x, 1)$ が答えとなります*3。
考察
一意性
まずは一意性に関して示します*4。
$p/q \equiv p'/q' \equiv x \pmod{m}$ とします。 $|p| \lt n$ かつ $0\lt q\lt d$ かつ $\gcd(p, q) = 1$ です。$p'$, $q'$ についても同様です。
このとき、$pq' \equiv p'q \pmod{m}$ です。 つまり、ある $i$ が存在して $pq' - p'q = i\cdot m$ が成り立ちます。 ところで $|pq'| \lt nd$ かつ $|p'q| \lt nd$ なので、$-2nd \lt pq' - p'q \lt 2nd$ です。 $2nd \le m$ ならば $-m \lt pq' - p'q \lt m$ であり、$i = 0$ となります。
以上から $pq' = p'q$ なので、$\gcd(p, q) = \gcd(p', q') = 1$ と合わせて $(p, q) = (p', q')$ を得ます。
解の性質
条件を満たす（一意な）解 $(p, q)$ が存在したとします。 ある $i$ が存在して $p+im = qx$ となります。$qm\ne 0$ で割って $$ \frac{x}{m} - \frac{i}{q} = \frac{p}{qm} $$ を得ます。$|p|\lt n$, $q\lt d$（問題設定）と $2nd \le m$（一意性の条件）から $n/m \lt 1/2q$ なので
$$ \left|\frac{p}{qm}\right| \le \frac{n}{qm} \lt \frac{1}{2q^2} $$
とわかります。
やや天下りですが、$\alpha$ が与えられているとき、Stern–Brocot 木を用いることで、$|i/q-\alpha| \lt 1/2q^2$ なる $i/q$ を（整数の組 $(i, q)$ の形で）列挙できることが知られています。 $\alpha = x/m$ は既知なので、Stern–Brocot 木によって $i/q$ を列挙し、$p = qx - im$ を計算して条件を満たすかを調べればよさそうです。
列挙は（ここでは $\alpha$ が分数の形で陽に与えられているので）一つあたり $O(1)$ 時間ででき、$x/m$ に到達するまでの個数は $O(\log(m))$ 個で抑えられるので、計算量は $O(\log(m))$ 時間でできそうです。
実装
Stern–Brocot 木は連分数展開だったり拡張互除法だったりと関係が深いので、そのうち得意なものを意識しながら実装するのがよいでしょう。 下記の実装例はややギャップがあるかもしれません。後日改善するかもしれません。
fn rat_convert(x: u64, m: u64, d: u64) -> Option<(u64, u64)> { let n = m / (2 * d); let mut u = (m, 0); let mut v = (x, 1); while v.0 != 0 && (v.0 >= n || v.1 >= d) { let q = u.0.div_euclid(v.0); let r = (u.0 - q * v.0, u.1 + q * v.1); u = std::mem::replace(&mut v, r); } (v.0 < n && v.1 < d).then_some(v) } assert_eq!(rat_convert(714236805, 998244353, 1000), Some((113, 355)));
関数名は元論文のものを拝借しました。ねずみ変換 🐀。ここでは $p \ge 0$ を仮定していそうな気がします。必要に応じて x の代わりに m - x を渡すといいかもしれません。
ねむいのであまり正当性に自信がありませんが、とりあえず $0\le p\le 10^3$ かつ $1\le q\le 10^3$ の全ケースについて $x = pq^{-1}\bmod {998244353}$ から再構成する単体テストは pass していました。
（追記）Stern–Brocot 木の探索っぽい素朴な形の実装です。
fn rat_convert(x: u64, m: u64, d: u64) -> Option<(u64, u64)> { let n = m / (2 * d); if x < n && 1 < d { return Some((x, 1)); } let mut l = (0, 1); let mut r = (1, 0); loop { let num = l.0 + r.0; let den = l.1 + r.1; let (i, q) = match (num * m).cmp(&(den * x)) { Less => { // num/den < x/m // k = max {k: m (l.0 * k * r.0) < x (l.1 + k * r.1)} // k = max {k: k (m r.0 - x r.1) < x l.1 - m l.0} let k = (x * l.1 - m * l.0 - 1) / (m * r.0 - x * r.1); l.0 += k * r.0; l.1 += k * r.1; l } Equal => return None, Greater => { // num/den > x/m // k = max {k: m (k l.0 + r.0) > x (k l.1 + r.1)} // k = max {k: m r.0 - x r.1 > k (x l.1 - m l.0)} let k = (m * r.0 - x * r.1 - 1) / (x * l.1 - m * l.0); r.0 += k * l.0; r.1 += k * l.1; r } }; if q * x < i * m { continue; } let p = q * x - i * m; if p < n && q < d { return Some((p, q)); } } }
参考文献
- Wang, Paul S. “A p-adic algorithm for univariate partial fractions." In Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, pp. 212–217. 1981.
- Wang, Paul S., M. J. T. Guy, and James H. Davenport. "P-adic reconstruction of rational numbers." ACM SIGSAM Bulletin 16, no. 2 (1982): 2–3.
- Rational reconstruction (mathematics) - Wikipedia
他にも、下記の記事や、その参考文献にある本を読むといいかもしれません。
特に、本文中で fact として扱った「既知の $\alpha$ に対して $|p/q-\alpha| \lt 1/2q^2$ なる $p/q$ を Stern–Brocot 木で列挙できる」という部分の証明などが、その本に載っています。
おわり
ばーっと書いたら記事ができあがってしまいました。とてもねむいです。
