题目来自LOJ。

就记一个公式，设f(n,k)为n!里分解得到的k（k为质数）的个数，则f(n,k)=f(n/k,k)+n/k。

证明很好证，显然我们要的只有k,k^2,k^3……这样的数有n/k个，然后往下递归即可。

至于k为合数，就质因数分解做就行。

k的质因子最多O(logk)个，递归显然是O(logn)的，因此复杂度为O(logklogn)，可以线性筛预处理素数通过。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=4e6+5;const ll INF=9e18;ll calc(ll n,ll p){ if(n
            
             n)break; he[i*su[j]]=1; if(i%su[j]==0)break; } }}ll n,k;int main(){ Euler(N-5); while(scanf("%lld%lld",&n,&k)!=EOF){ ll x=INF; for(int i=1;su[i]*su[i]<=k;i++){ if(k%su[i]==0){ ll cnt=0; while(k%su[i]==0)k/=su[i],cnt++; x=min(x,calc(n,su[i])/cnt); } } if(k>1)x=min(x,calc(n,k)); printf("%lld\n",x); } return 0;}
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++