【数论】小A进学校

小A进学校

题目描述

近日，清华大学挖出来一个明清古墓。小A决定冒充考古系科研人员去盗墓。他遇到的第一个难关是来自校门口保安的质疑，因为小没有清华学生证，所以保安决定通过问问题的方式验证小A的身份。

保安会说出两个整数n和k，小A需要回答的阶乘在进制下末尾零的个数。

输入

一行两个整数，表示n和k。

输出

一个整数表示n的阶乘在k进制下末尾零的个数。

样例输入

10 40

样例输出

提示

【题解】

　　进制为k，然后对k进行质因数分解即可，然后取每个质数，搜索有多少个，然后每个质数的个数之和，再取一个最小值即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll ;
 4 const int N = 2e6+10 ;
 5  
 6  
 7 /* Euler function */
 8 int prime[N] , cnt ;
 9 bool Is_prime[N];
10 void Euler(){
11     for( int i = 2 ; i < N ; i++ ){
12         if( !Is_prime[i] ){
13             prime[cnt++] = i ;
14         }
15         for( int j = 0 ; j < cnt && prime[j] * i < N ; j ++ ){
16             Is_prime[ prime[j] * i ] = true ;
17             if( i % prime[j] == 0 ){
18                 break;
19             }
20         }
21     }
22 }
23  
24  
25 ll n , k ;
26 ll A[N],B[N],C[N];
27 ll qpow( ll a , ll b ){
28     ll ans = 1 ;
29     while( b ){
30         if( b & 1 ) ans = ans * a ;
31         b >>= 1 ;
32         a = a * a ;
33     }
34     return ans ;
35 }
36 int main()
37 {
38     Euler() ;
39     /*
40     for( int i = 0 ; i < 10 ; i++ ){
41         printf("%d
",prime[i]);
42     }
43     */
44  
45     ios_base :: sync_with_stdio( false );
46     cin.tie(NULL) , cout.tie(NULL);
47     cin >> n >> k ;
48  
49     int tot = 0 ;
50     for( int i = 0 ; i < cnt && prime[i] * prime[i] <= k ; i++ ){
51         if( k % prime[i] == 0 ){
52             A[tot] = prime[i] ;
53             while( k % prime[i] == 0 ){
54                 k /= prime[i] ;
55                 B[tot] ++ ;
56             }
57             tot ++ ;
58         }
59     }
60  
61     if( k != 1ll ){
62         A[tot] = k ;
63         B[tot] = 1 ;
64         tot ++ ;
65     }
66  
67     for( int i = 0 ; i < tot ; i++ ){
68         ll tmp = A[i] ;
69         //cout << tmp << endl;
70         ll num = n / tmp ;
71         for( ; tmp <= n / A[i] ; ){
72             tmp = tmp * A[i] ;
73             num += n / tmp ;
74         }
75         tmp = qpow( A[i] , B[i] );
76         C[i] = num / B[i] ;
77         //cout << A[i] << " " << num << " " << tmp << " " << B[i] << endl;
78     }
79     ll ans = 0x7fffffffffffffff;
80     for( int i = 0 ; i < tot ; i++ ){
81         ans = min( ans , C[i] ) ;
82     }
83     cout << ans << endl ;
84     return 0;
85 }

View Code