洛谷10月月赛R1·浴谷八连测R1·提高组 SAC E#1 - 一道中档题 Factorial

发表于
  • Description 求$n!$在$k$进制下后缀$0$的个数.

老夫掐指一算，竟然掐到std算法？

  • Solution
    讲道理，刚开始看到这道题是不会做的。
    但是老夫想想如果$m=10$还是会做的。
    数数小于等于$n$有多少个5的倍数就行了。2的倍数绝对比5的倍数多嘛。
    于是我就有了一点想法。
    首先质因数分解少不了的。$m = \sum{i = 1}^k s_i^{cnt_i}$
    然后，对于每个质因数$s_i$，算一算$[1,n]$能找到多少它的倍数（不过类似计算2时遇到$2^3$这些要算三次的）
    怎么计算？容斥一下？应该只有我这种zz一开始这么想？
    后来发现计算的时候每次加1就行了，因为前面的都已经计算过了。
    算完之后，发现$s_i$在$[1,n]$中找到了$x_i$，但是出现一个$m$至少$s_i$要出现$cnt_i$次。所以最终答案就是$min\    {i=1}^{k}{\frac{x_i}{cnt_i} }$
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
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
LL n, m, tot ;
LL s[1010], cnt[1010] ;
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "a.in", "r", stdin ) ;
    freopen ( "a.out", "w", stdout ) ;
#endif
    LL i, j, x, ans, gn ;
    while ( scanf ( "%lld%lld", &n, &m ) != EOF ) {
        memset ( s, 0, sizeof s ) ;
        memset ( cnt, tot = 0, sizeof cnt ) ;
        for ( x = m, i = 2 ; i*i <= x ; i ++ ) {
            if (x%i == 0) s[++tot] = i ;
            while (x%i == 0) cnt[tot] ++, x /= i ;
        }
        if (x != 1) s[++tot] = x, cnt[tot] = 1 ;    
        /*printf ( "%lld = ", m ) ;
        for ( i = 1 ; i < tot ; i ++ ) printf ( "%lld^%lld + ", s[i], cnt[i] ) ;
        printf ( "%lld^%lld\n", s[tot], cnt[tot] ) ;*/
        ans = 1LL<<60 ;
        for ( i = 1 ; i <= tot ; i ++ ) {
            gn = 1 ;    
            x = 0 ; 
            for ( j = 1 ; gn <= n ; j ++ ) {
                gn *= s[i] ;
                x += n/gn ;
            }
            //printf ( "time %lld = %lld\n", s[i], x ) ;    
            ans = min(ans, x/cnt[i]) ;  
        }
        printf ( "%lld\n", ans ) ;  
    }
    return 0 ;
}