阶乘
题目描述
你醒了。
地上散落着写满文字的纸张,不远处的门紧紧锁着。
你试图寻找窗户,但是这里除了门,没有任何出口。
地上一张纸熠熠发光。你拾起它,上面写着一个大大的感叹号。
你忽然明白了什么。
众所周知,对于一个正整数\(N\),它的阶乘\(N!=\prod_{i=1}^Ni\)。特别的,\(0!=1\)。
小\(C\)在计算一个正整数\(N\)的阶乘,但是他只想知道在\(a\)进制下,运算结果的末尾有多少个\(0\)。
输入输出格式
输入格式
一行两个正整数\(N,a\)
输出格式
输出在\(a\)进制下,\(N!\)末尾的\(0\)的数量。
样例
输入
200 10
输出
59
数据范围
对于\(20\%\)的数据,有\(0\le N\le20\),\(0<a\le20\)。
对于\(20\%\)的数据,有特殊性质:对于任何一个\(a\)的素因数\(p\),有\(p^2\nmid a\)。
对于\(50\%\)的数据,有\(0\le N\le 10^6\),\(0<a\le10^6\)。
对于\(100\%\)的数据,有\(0\le N\le 10^{18}\),\(0\lt a\le 10^{12}\)。