問題一覧 > 通常問題

No.2177 Recurring ab

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

問題文

正整数 $N$ が与えられます。

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

  • $2 \leq p \leq 10^{9}$

  • $0 \leq a,b \leq \min(p,10) - 1$

  • $a \neq b$

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

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

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

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

制約

  • $1 \leq N \leq 10^{8}$

  • $N$ は整数

入力

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

$N$
  • $1$ 行目には $N$ が与えられる

出力

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

サンプル

サンプル1
入力
2
出力
355

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

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

サンプル2
入力
1
出力
0

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

サンプル3
入力
100000000
出力
40500192564

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

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