問題一覧 > 通常問題

No.1936 Rational Approximation

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 79
作問者 : noya2 / テスター : kotatsugame tatyam tassei903
お気に入りにしたユーザー ProblemId : 7208 / 自分の提出
問題文最終更新日: 2022-05-11 00:25:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 343 (順位表) の他の問題:

Problem Statement

For any positive rational number $u$, there exists a unique pair of coprime positive integers $(p,q)$ such that $\displaystyle u = \frac{p}{q}$, so we denote such $(p,q)$ by $(\ p(u),q(u)\ )$.

You are given $2$ coprime integers $P,\ Q\ (2\le P\lt Q)$.

Among the pairs of rational numbers $(L,\ R)$ satisfying both of the following conditions, the one minimizing $R-L$ is unique, so we denote such $(L,\ R)$ by $(L_{\max},\ R_{\min})$.

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

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

Find $p(L_{\max}) + q(L_{\max}) + p(R_{\min}) + q(R_{\min})$.

Constraints

  • All input values are integers.
  • $2\le P\lt Q\le 10^9$
  • $P,\ Q$ are coprime.

    • Input

    $P\ Q$

    Output

    Print the answer on $1$ line.

    Sample

    Sample 1
    Input
    2 3
    Output
    5

    We have $\displaystyle L_{\max} = \frac{1}{2},\ R_{\min} = 1$.

    Since $p(L_{\max}) = 1,\ q(L_{\max}) = 2,\ p(R_{\min}) = 1,\ q(R_{\min}) = 1$, print their sum, $5$.

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