問題一覧 > 通常問題

No.2368 I love a square root of 2

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 36
作問者 : Carpenters-Cat / テスター : logx shobonvip Kak1_n0_tane comavius
お気に入りにしたユーザー ProblemId : 6678 / 自分の提出
問題文最終更新日: 2023-06-30 19:20:17
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 395 (順位表) の他の問題:

Problem

Today is Pina's birthday.

Pina loves $\sqrt{2}$.

So Pina considered the set $A$ of real numbers $X$ satisfying the following condition.

  • It can be expressed as $X = a + \sqrt{2}b$ using integers $a, b$ that are at least $0$.

Answer the following question about this set $A$.

  • What is the value of the $N$-th smallest element of $A$?
  • Input

    $N$
    

    The input is given from Standard Input in the above format.

    Here, $N$ is an integer satisfying $1 \leq N \leq 10^{10}$.

    Output

    $p\ q$
    

    The answer to the problem can be expressed as $p + \sqrt{2}q$ using integers $p, q$, so print the two integers $p, q$ as shown above.

    It can be proved that $p, q$ are uniquely determined under these constraints.

    Sample

    Sample 1
    Input
    1
    Output
    0 0

    The smallest element of the set $A$ is $0$, which can be expressed as $0 + \sqrt{2}\times 0$.

    Sample 2
    Input
    6
    Output
    0 2

    The elements of the set $A$, in ascending order, are $0,\;1,\;\sqrt{2},\;2,\;1+\sqrt{2},\; 2\sqrt{2},...$, and

    the value of the 6th smallest element can be expressed as $0 + \sqrt{2} \times 2$.

    Sample 3
    Input
    10000000000
    Output
    31063 96955

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