Hide

# Problem E

Meow Factor

Picture via
pxhere, cc0

*meow factor*. For a positive integer $n$, its meow factor is the largest integer $m$ such that $n$ is evenly divisible by $m$ nine times (once for each life of a cat). We say that $n$ is divisible by $m$ nine times if, starting with $n$, you can divide it by $m$ without a remainder, take the result of the division and again divide it by $m$ without a remainder, and so on, dividing by $m$ nine times in total.

While some cats are naturally chic and have an innate ability to see the meow factor of numbers, others who struggle to stay in vogue can not even tell the difference between $3\, 584$ and $4\, 711$ (the former clearly having a higher meow factor). Can you help those poor unfortunate cats lacking a sense of style, by writing a program to determine the meow factor of a number?

## Input

The input contains a single integer $n$ ($1 \le n \le 2^{63}-1$).

## Output

Output the meow factor of $n$.

Sample Input 1 | Sample Output 1 |
---|---|

3584 |
2 |

Sample Input 2 | Sample Output 2 |
---|---|

4711 |
1 |

CPU Time limit
1 second

Memory limit
1024 MB

Statistics
Show

Downloads

Author

Source
Kattis Challenge 2017