UVA-10061 How many zero's and how many digits ? （数论）-白红宇

UVA-10061 How many zero's and how many digits ? （数论）

阅读量：5294 次

发布时间：2019-06-14

本文共 1446 字，大约阅读时间需要 4 分钟。

题目大意：让求n！在base进制下的位数以及末尾0的连续个数。

题目分析：一个m位的b进制数N，最小是b^(m-1)，最大不超过b^m，即b^(m-1)≤N<b^m。解不等式，得log10(N)/log10(b)<m≤log10(N)/log10(b)+1。

至于0的个数，要对n！分解质因数，对base分解质因数。看n！的质因数中能凑出多少个base。能凑出的base的个数就是末尾0的个数。设n！与base的共同质因数所构成的集合为s1。base的质因数构成的集合为s2，则末尾0的个数就是min(s1(s2(i))/s2(i))。

其实，这道题无非就是多个算法的整合。筛素数+大整数分解质因数。

代码如下：

# include
     
      # include
      
       # include
       
        # include
        # include
         
          # include
          
           using namespace std;const int N=1<<20;double a[N+50];int pri[150],mark[800];map
           
            m[805];void init(){ a[1]=log10(1.0); for(int i=2;i<=N;++i) a[i]=a[i-1]+log10(i); for(int i=2;i<=800;++i){ int n=i; int a=2; while(a*a<=n){ while(n%a==0){ ++m[i][a]; n/=a; } ++a; } if(n>1) ++m[i][n]; } pri[0]=0; memset(mark,0,sizeof(mark)); for(int i=2;i<=800;++i){ if(!mark[i]) pri[++pri[0]]=i; for(int j=1;j<=pri[0]&&i*pri[j]<=800;++j){ mark[i*pri[j]]=1; if(i%pri[j]==0) break; } }}int f(int n,int k){ map
            
             mp; for(int i=2;i<=n;++i){ int n=i; for(int j=1;j<=pri[0]&&pri[j]<=k;++j){ while(n%pri[j]==0){ ++mp[pri[j]]; n/=pri[j]; } } } map
             
              ::iterator it; int ans=1<<30; for(it=m[k].begin();it!=m[k].end();++it){ ans=min(ans,mp[it->first]/(it->second)); } return ans;}int g(int n,int k){ double ans=a[n]/log10(k)+1.0; return (int)ans;}int main(){ init(); int n,k; while(scanf("%d%d",&n,&k)!=EOF) { printf("%d %d\n",f(n,k),g(n,k)); } return 0;}

转载于:https://www.cnblogs.com/20143605--pcx/p/4714749.html

你可能感兴趣的文章

2014-04-21-阿里巴巴暑期实习-后台研发-二面经验