题解 CF1114C 【Trailing Loves (or L'oeufs?)】
皎月半洒花
2019-03-02 07:35:14
一道比较简单的题……但是我当时写挂了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`赛神仙（
```cpp
#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 ;
}
```