题目

求十进制 \(n!\) 在 \(m\) 进制下末尾 \(0\) 的个数

分析

签到题

只要看 \(n!\) 有多少个 \(m\) 的倍数就好了

考虑分解 \(m\) 的质因子

然后根号计算每个因子在 \(n!\) 中有多少个

取能取到的最小值就行了

\(Code\)

#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int vis[N] , pr[N] , tot , cnt;

LL zhi[N] , hav[N] , num[N];

inline void getprime()

{

	vis[1] = 1;

	for(register int i = 2; i <= N - 5; i++)

	{

		if (!vis[i]) pr[++tot] = i;

		for(register int j = 1; j <= tot && i * pr[j] <= N - 5; j++)

		{

			vis[i * pr[j]] = 1;

			if (i % pr[j] == 0) break;

		}

	}

}

int main()

{

	getprime();

	int T; LL n , m;

	scanf("%d" , &T);

	for(; T; T--)

	{

		cnt = 0;

		scanf("%lld%lld" , &n , &m);

		for(register int i = 1; i <= tot; i++)

		if (m % pr[i] == 0)

		{

			num[++cnt] = pr[i] , zhi[cnt] = 0;

			while (m % pr[i] == 0)  zhi[cnt]++ , m /= pr[i];

		}

		if (m != 1 && m) num[++cnt] = m , zhi[cnt] = 1;

		LL ans = 9e18;

		for(register int i = 1; i <= cnt; i++)

		{

			LL s = num[i];

			hav[i] = 0;

			while (n >= s)

			{

				hav[i] += n / s;

				if (s <= n / (LL)num[i]) s = s * (LL)num[i];

				else break;

			}

			if (hav[i] / zhi[i] < ans) ans = hav[i] / zhi[i];

		}

		printf("%lld\n" , ans == 9e18 ? 0 : ans);

	}

}

巴特西

JZOJ 3566. 【GDKOI2014】阶乘

题目

分析

\(Code\)

最新文章

热门文章