No.2177 Recurring ab
MasKoaTS
p-adicProblem Statement
You are given a positive integer $N$.
Find the number of integer triples $(p,a,b)$ that satisfy all of the following conditions.
$2 \leq p \leq 10^{9}$
$0 \leq a,b \leq \min(p,10) - 1$
$a \neq b$
There exists a rational number $x$ such that all of the following conditions hold.
$\displaystyle x > \dfrac{1}{N}$
$x$ is equal to the value of the recurring decimal "$0.ababab \cdots$" interpreted in base $p$.
Formally, $0 < x < 1$, and for every positive integer $k$, the remainder when $\lfloor p^{2 k} x \rfloor$ is divided by $p^{2}$ is equal to $p a + b$.
Here, $\lfloor t \rfloor$ denotes the greatest integer not exceeding $t$.
Constraints
$1 \leq N \leq 10^{8}$
$N$ is an integer
Input
The input is given in the following format.
$N$
Line $1$ contains $N$.
Output
Output the answer on $1$ line.
Sample
Sample 1
Input
2
Output
355
For example, $(p,a,b) = (2,1,0)$ satisfies the conditions, because the rational number $x$ written as "$0.101010 \cdots$" in base $2$ satisfies $$x = \dfrac{2}{3} > \dfrac{1}{2}$$ .
On the other hand, for $(p,a,b) = (5,3,3)$, the rational number $x$ written as "$0.333333 \cdots$" in base $5$ satisfies $$x = \dfrac{3}{4} > \dfrac{1}{2}$$ , but $a \neq b$ does not hold, so it is not counted among the triples $(p,a,b)$ satisfying the conditions.
Sample 2
Input
1
Output
0
No integer triple satisfies the conditions.
Sample 3
Input
100000000
Output
40500192564
The answer may not fit in a 32-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。