题解 CF1114C 【Trailing Loves (or L'oeufs?)】

· · 题解

一道比较简单的题……但是我当时写挂了qaq

我们发现对于一个数n，在k(k\geq 2)进制下，其中后导0的个数其实就是

n = k^p\cdot w

保证p极大，那么p就是答案。

现在是阶乘的话，就需要我们先分解一下B，然后枚举质因数，算一下\log_{p_i}N，然后对于所有的幂都算出贡献，然后对所有质因数的res取min，然后就完了。

对了，先有long long后有天，Inf不开1e18赛神仙（

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std ;

#define ll long long
#define MAXN 3000000
#define Inf 1e18

double Log ;
ll Ans = 1ll * 4 * Inf, N, B, T, Fac[MAXN], Gs[MAXN], t, i, tot, j ; 

int main(){
    cin >> N >> B ;
    ll root = sqrt(B) + 1 ; 
    for (i = 2 ; i <= root ; ++ i){
        if (B % i) continue ;  T = 0 ;
        while (!(B % i)) B /= i, ++ T ; Gs[++ tot] = T, Fac[tot] = i ; 
    }
    if (B > 1) Fac[++ tot] = B, Gs[tot] = 1 ; Log = log((double)N) ; 
    for (i = 1 ; i <= tot ; ++ i){ 
        T = 0, t = Fac[i] ; 
        int u = (ll)((double)log((double)N) / log((double)t)) ;
        for (j = 1 ; j <= u ; ++ j, Fac[i] *= t) T += N / Fac[i] ;
        Ans = min(Ans, T / Gs[i]) ;
    }
    cout << Ans << endl ;
}