题目描述

输入

第一行有一个正整数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

解法

题意转化为：令n!=basei∗k，则i为答案；

同时称i为base在n!中的贡献。

直接想法是把base分解质因数为a1k1∗a2k2∗...∗amkm；

然后检查每个质因数ai在n!中的贡献 cnt，于是就可以得出这个质因数最多容纳cnt/ki个base。

把所有容纳能力取个最小值即为答案。

问题在于我们在求ai在n!中的贡献时，可能需要O(nlogn)的时间：

枚举j属于[1..n]，易得ai在j中的贡献，累计所有贡献即为ai在n!中的贡献。

如果采用上述办法，时间会超限。

给n一直除素数，并将每一次的商加起来，即为答案。

时间复杂度为O(logn)；

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="ex3566.in";

const char* fout="ex3566.out";

const int inf=0x7fffffff;

const int maxn=100007;

ll n,m,limit,tmp,tmd,tmb,ans;

ll t,i,j,k;

ll yue[maxn],cnt[maxn];

int main(){

    scanf("%d",&t);

    for (;t;t--){

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

        limit=(ll)sqrt(m);

        tmp=m;

        yue[0]=0;

        for (i=2;i<=limit;i++){

            if (tmp==1) break ;

            if (tmp%i==0){

                yue[++yue[0]]=i;

                cnt[yue[0]]=0;

                while (tmp%i==0){

                    cnt[yue[0]]++;

                    tmp/=i;

                }

            }

        }

        if (tmp>1) yue[++yue[0]]=tmp,cnt[yue[0]]=1;

        ans=0;

        for (i=1;i<=yue[0];i++) {

            //ll num=(n/yue[i]),fi=1,la=fi+num-1;

            tmd=0;

            /*for (j=yue[i];j<=n;j+=yue[i]) {

                k=j;

                while (k%yue[i]==0) k/=yue[i],tmd++;

            }*/

            k=n;

            while (k) k/=yue[i],tmd+=k;

            if (ans) ans=min(ans,tmd/cnt[i]);

            else ans=tmd/cnt[i];

            /*if (ans) ans=min(ans,(fi+la)*num/2/cnt[i]);

            else ans=(fi+la)*num/2/cnt[i];*/

        }

        printf("%lld\n",ans);

    }

    return 0;

}

启发

考虑把所有数一起处理，可以节省时间。