No.2177 Recurring ab
タグ : / 解いたユーザー数 85
作問者 :
MasKoaTS
/ テスター :
👑 
p-adic
👑 
potato167
問題文
正整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。