Problem F
Níulegasti grunnurinn
Languages
en
is
Jörmunrekur was playing around with writing some numbers in different bases. He started by trying $203433$. His favourite number is nine, so he doesn’t particularly care for this number. But if he writes it in base $16$ it becomes $31AA9$ which is a clear improvement since one of the digits is now nine. If he writes it in base $12$ it becomes $99889$ which is even better. Great even, three nines, you could hardly ask for something better. Or can you?
Input
The input is a single line containing two integers $1 \leq n, d \leq 10^{18}$. The integer $n$ is the number to be written out in some base and the integer $d$ is the digit Jörmunrekur wants to maximize the occurrences of. Only bases $\geq 2$ should be considered.
Output
Print how often $d$ can appear at most if the right base is chosen.
Scoring
|
Group |
Points |
Constraints |
|
1 |
40 |
$1 \leq n, d \leq 10^6$ |
|
2 |
30 |
$1 \leq n, d \leq 10^{12}$ |
|
3 |
30 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
203433 9 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
48899 4 |
2 |
