問題一覧 > 通常問題

No.2368 I love a square root of 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : Carpenters-CatCarpenters-Cat / テスター : logxlogx shobonvipshobonvip Kak1_n0_taneKak1_n0_tane comaviuscomavius
0 ProblemId : 6678 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-30 19:20:17

問題

今日はぴなさんの誕生日です。

ぴなさんは$\sqrt{2}$が大好きです。

そこで、ぴなさんは以下の条件を満たす実数$X$の集合$A$を考えました。

  • $0$以上の整数$a, b$を用いて、$X = a + \sqrt{2}b$と表せる。

この集合$A$について、以下の質問に答えてください。

  • 小さい方から数えて$N$番目の$A$の要素の値は何ですか？

    • 入力

    $N$

    入力は上の形式で、標準入力から与えられます。

    ただし$N$は整数であり、$1 \leq N \leq 10^{10}$を満たします。

    出力

    $p\ q$

    問題の答えは整数$p, q$を用いて$p + \sqrt{2}q$と表せるので、2つの整数$p, q$を上のように出力してください。

    なお、この制約中で$p, q$は一意に定まることが証明できます。

    サンプル

    サンプル1
    入力
    1
    出力
    0 0

    集合$A$の要素で一番小さいものは、$0$ で、これは$0 + \sqrt{2}\times 0$と表せます。

    サンプル2
    入力
    6
    出力
    0 2

    集合$A$の要素は、小さい順に$0,\;1,\;\sqrt{2},\;2,\;1+\sqrt{2},\; 2\sqrt{2},...$であり、

    小さい方から6番目の要素の値は$0 + \sqrt{2} \times 2$と表せます。

    サンプル3
    入力
    10000000000
    出力
    31063 96955

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