codeforces 1114C

   题目连接 : https://codeforces.com/contest/1114/problem/C

  题目大意:给一个整数n(1e18>=n>=0),和一个整数k(1e12>=k>=2),问n!在k进制情况下末尾有多少个0.

  题目很好理解,思路也很有意思,首先n!在十进制下有多少个0,很好想,10分解质因数有2,5,无论在什么情况下n!中分解出5的个数比2多,

分解是这个意思,5能找出1个5,10能找出一个5,25能找出2个5(因为是5*5,可以被5除两次)。以此类推,找这个东西是log级的。

代码如下:

sum=0;//分解出5的个数
    d=5;//因为要分解5所以是5
    while(d<=n){
        sum+=n/d;
        d*=5;
    }

进一步推广,要分解k进制,首先k分解质因数,在这里有一个问题,我们只是单单的找质因数中最大的就可以么,这个不一定,我们不知道最大的质因数要

多少个能组成k,虽然说质因数中最大的一定是数量最小的之一,但组成k需要的个数可能会让其他数不够用,比如48,有4个2,和1个3,在4!情况下,有3个2和1个3

这时反而2不够用,那么我们就要记录所有的质因数和需要的个数,然后每个都去找,看看那个最小的就是末尾0 的个数

AC代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
//map<int,int> mp;
#define INT_MAX 1e18;
typedef struct W_w{
    ll shu;
    ll ge;
}miao;
miao x[500010];
int main()
{
    ll m,n;
    scanf("%I64d %I64d",&m,&n);
    int d=sqrt(n);
    int ge=0;
    memset(x,0,sizeof(x));
    for(ll i=2;i<=d;i++){
        int flag=0;
        while(n%i==0){
            flag=1;
            x[ge].shu=i;
            x[ge].ge++;
            n/=i;
        }
        if(flag==1) ge++;
    }
    if(n!=1){
        x[ge].shu=n;
        x[ge].ge=1;
        ge++;
    }
    ll minn=INT_MAX;
    //printf("%d\n",ge);
    for(int i=0;i<ge;i++){
        ll dd=x[i].shu;
        int ha=0;
        while(dd){
            ha++;
            dd/=10;
        }
        dd=x[i].shu;
        ll sum=0;
        while(dd<=m){
            sum+=m/dd;
            int haha=0;
            ll ddd=dd;
            while(ddd){
                ddd/=10;
                haha++;
            }
            if(haha+ha>19) break;
            dd*=x[i].shu;
        }
        minn=min(minn,sum/x[i].ge);
    }
    printf("%I64d",minn);
    return 0;
}

 

上一篇:分享三十七kindle风xue追击 清单ge命 囚鸟 投zi异类 我の前ban生 早期*:秦与汉mobi


下一篇:High&NewTech:动图看1997~2019年《世界最有价值公司Top10排名》的变迁史——《Most Valuable Companies In The World》