$$阶乘\left(\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\right)$$

题目链接：$\mathrm{S}\mathrm{S}\mathrm{L}比赛1490$

题目

输入

第一行有一个正整数 $T,$ 表示测试数据的组数。
接下来的 $T$ 行，每行输入两个十进制整数 $n$ 和 $base$ 。

输出

对于每组数据，输出一个十进制整数，表示在 $base$ 进制下， $n!$ 结尾的零的个数。

样例输入

2

10 10 

10 2

样例输出

2

8

数据范围

对于 $20\%$ 的数据， $n<=20,base<=16$

对于 $50\%$ 的数据， $n<=10^9,base<=10^5$

对于 $100\%$ 的数据， $1<=T<=50，0<=n<=10^{18}，2<=base<=10^{12}$

思路

这道题是一道数学题。

我们可以分解 $base$ 质因数 $a_i$ 序列和每个质因数的个数 $b_i$，可以先用素数筛选法预处理出素数来减少运算时间。
接着就看 $n!$ 里面有多少个 $a_i$ ，然后再除以 $b_i$ ，就是 $base$ 的因数 $a_i^{b_i}$ 在 $n!$ 有的个数。找到这些数里面的最小值，就是答案。

那怎么求出 $n!$ 里面有多少个 $a_i$ 呢？
就 $n/a_i^1+n/a_i^2+n/a_i^3+\dots$ 。

记得用 $longlong$ 。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

ll T, n, base, time, ans, su[1000001];
ll tmp, fen[100001], mi[100001];
bool susu[1000001];

int main() {
	susu[0] = susu[1] = 1;//素数筛选法求出素数
	for (int i = 2; i <= 1000000; i++)
		if (!susu[i]) {
			su[++su[0]] = i;
			for (int j = i + i; j <= 1000000; j += i)
				susu[j] = 1;
		}
	
	scanf("%lld", &T);//读入
	for (int times = 1; times <= T; times++) {
		ans = 9223372036854775807;//初始化
		memset(mi, 0, sizeof(mi));
		memset(fen, 0, sizeof(fen));
		
		scanf("%lld %lld", &n, &base);//读入
		
		tmp = base;
		for (ll i = 1; i <= su[0]; i++)//分解质因数
			if (tmp != 1) {
				if (tmp % su[i] == 0) {
					fen[++fen[0]] = su[i];
					while (tmp % su[i] == 0) {
						mi[fen[0]]++;
						tmp /= su[i];
					}
				}
			}
			else break;
		if (tmp > 1) {
			fen[++fen[0]] = tmp;
			mi[fen[0]] = 1;
		}
		
		for (ll i = 1; i <= fen[0]; i++) {//求出n!中有分别多少个base的每个质因数
			tmp = n;
			time = 0;
			while (tmp) {
				tmp /= fen[i];
				time += tmp;
			}
			ans = min(ans, time / mi[i]);//找到除以base的这个质因数的个数之后数量最少的那个
		}
		
		printf("%lld\n", ans);//输出
	}
	
	return 0;
}