【JZOJ】 3566. 【GDKOI2014】阶乘

题目

---

题目描述

---

输入：

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

---

样例输入：

2
10 10
10 2

---

输出：

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

---

样例输出：

2
8

---

数据范围：

对于20%的数据，n<=20,base<=16
对于50%的数据，n<=10^9,base<=105
对于100%的数据，1<=T<=50，0<=n<=10^{18，2<=base<=10}12

---

---

题解

题目大意：

对于给定的n，计算出阶乘并转换为base进制，求有多少后缀0.

解题思路：

看到题目，很容易想到乘积因子，对于一个base进制下的数，想要得到一个零，需要在因数的因子中具有每一个base的因子。

（如 5！的 10进制，10的因子有 10=2*5, 而 5！有一个4和一个2，并有一个5，可分为3个2和一个5，故能配成一对，有一个后缀零。）

因此可以通过找base的因子与n的因子配对解决，答案则是最小的对数。

实现：

base的因子可以通过根号base的时间暴力枚举，如果最后没除尽，那最后的base余数是质数，答案直接加上就行。

找对应的因子可通过整除n找出，如果有一个数内有多个对应因子，则将因子乘方后在整除，直到大于n即可。

提醒：C++用户记得开long long，pascal用户要开int64。

---

---

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long T,i,j,k,n,m,sum,bz,ans,a[100005],ad[100005];
int main()
{
    scanf("%lld",&T);
    while (--T>=0)
    {
        scanf("%lld%lld",&n,&m);
        sum=0,ans=0;
        for (i=2;i<=sqrt(m);++i)
		{
            if (m%i==0)
			{
                a[++sum]=i;
                ad[sum]=0;
                while (m%i==0)
				{
                    ++ad[sum];
                    m=m/i;
                }
            }
            if (m==1) break;
        }
        if (m>1) a[++sum]=m,ad[sum]=1;
        for (i=1;i<=sum;++i) 
		{
            bz=0,k=n;
            while (k) k=k/a[i],bz+=k;
            if (ans) ans=min(ans,bz/ad[i]); else ans=bz/ad[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}