問題一覧 > 通常問題

No.1936 Rational Approximation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 62
作問者 : noya2noya2 / テスター : tassei903tassei903 kotatsugamekotatsugame tatyamtatyam
12 ProblemId : 7208 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-11 00:25:26

問題文

任意の正の有理数 $u$ について、$\displaystyle u = \frac{p}{q}$ となる互いに素な正整数の組 $(p,q)$ が唯一存在するので、 このような $(p,q)$ を $(\ p(u),q(u)\ )$ と表します。

互いに素な $2$ つの整数 $P,\ Q\ (2\le P\lt Q)$ が与えられます。

以下の条件をともに満たす有理数の組 $(L,\ R)$ のうち $R-L$ が最小のものは唯一存在するので、 このような $(L,\ R)$ を $(L_{\max},\ R_{\min})$ とします。

  • $1\le q(L),\ q(R)\lt Q$

  • $\displaystyle 0\lt L\lt \frac{P}{Q}\lt R$

$p(L_{\max}) + q(L_{\max}) + p(R_{\min}) + q(R_{\min})$ を求めてください。

制約

  • 入力はすべて整数
  • $2\le P\lt Q\le 10^9$
  • $P,\ Q$ は互いに素
  • 入力

    $P\ Q$
    

    出力

    答えを $1$ 行で出力してください。

    サンプル

    サンプル1
    入力
    2 3
    出力
    5

    $\displaystyle L_{\max} = \frac{1}{2},\ R_{\min} = 1$ です。

    $p(L_{\max}) = 1,\ q(L_{\max}) = 2,\ p(R_{\min}) = 1,\ q(R_{\min}) = 1$ より、これらの和である $5$ を出力します。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。