题目描述
近日,清华大学挖出来一个明清古墓。小A决定冒充考古系科研人员去盗墓。他遇到的第一个难关是来自校门口保安的质疑,因为小没有清华学生证,所以保安决定通过问问题的方式验证小A的身份。
保安会说出两个整数n和k,小A需要回答的阶乘在进制下末尾零的个数。
保安会说出两个整数n和k,小A需要回答的阶乘在进制下末尾零的个数。
输入
一行两个整数,表示n和k。
输出
一个整数表示n的阶乘在k进制下末尾零的个数。
样例输入
10 40
样例输出
2
提示
【题解】
进制为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\n",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 }