ABC 401-500/ABC408G - A／B < p／q < C／D - 競技プログラミング用 知識集積所

---

問題

ABC408G

必要知識

B以下レベルの内容は省略

• Farey数列
• 多倍長整数型（未作成）

考え方

Farey数列による正実数の有理数近似の知識を使う。
とりあえず、そのアルゴリズムの紹介。

2つの規約分数a/bとc/dの中間数を(a+c)/(b+d)と定める。

まず、2つの分数0/1と1/0を用意する。（後者は厳密には分数ではないが）
この2つの中間数1/1を求める。
これが目標の数より小さい場合、小さい方の分数をこの中間数に入れ替える。
これが目標の数より大きい場合、大きい方の分数をこの中間数に入れ替える。
必要なだけ繰り返すと、目標数に近い有利数が得られる。

例えば√2を近似する場合、

• 初期状態として、0/1 < √2 < 1/0
• 中間数1/1は√2より小さいので、1/1 < √2 < 1/0
• 中間数2/1は√2より大きいので、1/1 < √2 < 2/1
• 中間数3/2は√2より大きいので、1/1 < √2 < 3/2
• 中間数4/3は√2より小さいので、4/3 < √2 < 3/2
• 中間数7/5は√2より小さいので、7/5 < √2 < 3/2
• 中間数10/7は√2より大きいので、7/5 < √2 < 10/7

以下、必要なだけ繰り返せば、必要なだけよい近似値が得られる。
そして、例えば最後の7/5 < √2 < 10/7という範囲であれば、この中に分母が7未満の有理数が存在しないことが保証される。

今回の問題では2つの数を両方挟んだままこのFarey数列での近似を行い、中間値が両者を分けた瞬間、その分母が答えるべき値である。
例えば 4/7と5/8であれば、

• 初期状態として、0/1 < 4/7 < 5/8 < 1/0
• 中間数1/1は5/8より大きいので、0/1 < 4/7 < 5/8 < 1/1
• 中間数1/2は4/7より小さいので、1/2 < 4/7 < 5/8 < 1/1
• 中間数2/3は5/8より大きいので、1/2 < 4/7 < 5/8 < 2/3
• 中間数3/5は4/7と5/8の間なので、1/2 < 4/7 < 3/5 < 5/8 < 2/3

このとき、1/2 < 4/7 < 3/5 範囲にも 3/5< 5/8 < 2/3 範囲にも分母が5未満の有理数は存在しないので、4/7 < x < 5/8 範囲にある有理数の分母の最小値は5である。

ということで、これを実装してやればよいのだが、難点が2つ。

1つは、分数の大小判定をどうするか。
double型では精度が不安なので（また、1/0が扱えないので）、判定は分母を払って整数型で行いたい。
しかし、値が10^18までということは、積は10^36まで覚悟せねばならず、long long型でも足りない。
仕方がないので、コードの先頭に

# include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

を書き足して多倍長整数型（未作成）を導入し、int128_t型を使うことにする。
（無限桁の多倍長を扱うとTLEする）

もう1つは、実行時間の問題。
1/10^18のような分数を持ってこられると、大きい方を更新しながら中間数を10^18回とることになってTLEする。
そこで、手計算で「同じ側の更新を何連続で行うことになるか」を求める式を作り、その回数分まとめて中間数の処理を行うようにする。

この2つを解消できればACできる。

解答例

解答例

注意点

別解

連部数展開を用いる

公式解法参照。
Farey数列とは縁深いものなので類似解法ではあるが、連部数展開だとlong long型で収まるらしい。