codeforces-#538-C

codeforces-#538-C

七月 08, 2020

C. Trailing Loves (or L’oeufs?)

题意
求n!在b进制下末尾连续0的长度

题解

要求 n! 在 b 进制下有多少个尾 0 就相当于 求 n! % (b^k) == 0 的最大 k。
那么我们现在把 n! 看作一个数 A。问题就是 求 A % (b^k) == 0 的最大 k;
我们知道有素数分解定理： b = p1^a1 p2^a2 p3^a3 …；
那么我们如果可以求得 A 里面 p1^b1 p2^b2 p3^b3 … 的 b1, b2, b3…
那么答案 ans = min(ans, ai/bi ) 了也就是要整除，首先要满足最小的那个能整除

(1)首先对 b 进行素因子分解，直接暴力（log b）, 用一个数组离散化形成该素因子的编号和该素因子的幂的映射 或者 用map存储该素因子的幂，得到所有素因子以及素因子的幂
(2)对于每一个素因子p，计算对应的 A（即 n! ) 中素因子p的幂，两者相除取所有p幂的最小值就是对应的最大整数。

问题在于如何快速求得n!即A的所有素因子个数
这里求 n! 下 素因子 p 的幂 用累除法，因为存在推论：
n！ 下 p 的幂 = [ n/p ] + [ n/(p^2) ] + [ n/(p^3) ] …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# include <bits/stdc++.h>

 using namespace std;
 typedef long long ll;
 vector<ll>prime;
 map<ll,int>powcnt;
///一个数的素因子及其幂的logn求法
 void getprime(ll num){
    for(ll i=2;i*i<=num;i++){
        if(num%i==0){
            prime.push_back(i);
            while(num%i==0){
                num/=i;
                powcnt[i]++;
            }
        }
    }
    if(num!=1){
        prime.push_back(num);
        powcnt[num]++;
    }
 }
///求n!中某一素因子的幂
 ll func(ll p,ll n){
    ll ans=0;
    while(n){
        ans+=n/p;
        n/=p;
    }
    return ans;
 }
 int main(){
    ll n,b;cin>>n>>b;
    getprime(b);
    ll ans=(ll)1e18;
    int len=prime.size();
    for(int i=0;i<len;i++){
        ans=min(ans,func(prime[i],n)/powcnt[prime[i]]);
    }
    cout<<ans<<endl;
 }