問題一覧 > 通常問題

No.2177 Recurring ab

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 88
作問者 : MasKoaTS / テスター : 👑 p-adic 👑 potato167
4 ProblemId : 8543 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-15 23:37:01

問題文

正整数 NN が与えられます。

次の条件をすべて満たす整数の組 (p,a,b)(p,a,b) の個数を求めてください。

  • 2≤p≤1092 \leq p \leq 10^{9}

  • 0≤a,b≤min⁡(p,10)−10 \leq a,b \leq \min(p,10) - 1

  • a≠ba \neq b

  • ある有理数 xx が存在し、次の条件がすべて成り立つ。

    • x>1N\displaystyle x > \dfrac{1}{N}

    • xx は循環小数「0.ababab⋯0.ababab \cdots」を pp 進法で解釈した値に等しい。

      厳密には、0<x<10 < x < 1 であり、かつ任意の正整数 kk に対して、⌊p2kx⌋\lfloor p^{2 k} x \rfloor を p2p^{2} で割った余りが pa+bp a + b に等しい。
      ただし、⌊t⌋\lfloor t \rfloor は tt を超えない最大の整数を表す。

制約

  • 1≤N≤1081 \leq N \leq 10^{8}

  • NN は整数

入力

入力は次の形式で与えられます。

NN

  • 11 行目には NN が与えられる

出力

答えを 11 行に出力してください。

サンプル

サンプル1
入力
2
出力
355

例えば (p,a,b)=(2,1,0)(p,a,b) = (2,1,0) は、22 進法表記で「0.101010⋯0.101010 \cdots」となる有理数 xx について、 x=23>12x = \dfrac{2}{3} > \dfrac{1}{2} が成り立つので、条件を満たします。

一方、(p,a,b)=(5,3,3)(p,a,b) = (5,3,3) は、55 進法表記で「0.333333⋯0.333333 \cdots」となる有理数 xx について、 x=34>12x = \dfrac{3}{4} > \dfrac{1}{2} が成り立ちますが、a≠ba \neq b ではないので、条件を満たす (p,a,b)(p,a,b) の組に含まれません。

サンプル2
入力
1
出力
0

条件を満たす整数の組は存在しません。

サンプル3
入力
100000000
出力
40500192564

答えは32bit整数型に収まらない可能性があります。

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