/ WAOI / 题库 /

阶乘

阶乘

题目描述

你醒了。

地上散落着写满文字的纸张,不远处的门紧紧锁着。

你试图寻找窗户,但是这里除了门,没有任何出口。

地上一张纸熠熠发光。你拾起它,上面写着一个大大的感叹号。

你忽然明白了什么。

众所周知,对于一个正整数\(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}\)。

信息

ID
1000
难度
3
分类
数论 点击显示
标签
(无)
递交数
3
已通过
1
通过率
33%
被复制
1
上传者