当前位置:编程学习 > C/C++ >>

GCPC2011 - A Faculty Dividing Powers

题意是说给出n , k 求出最大的 i 使得 n! % k^i == 0 ...
     假设最简单的情况...k是质数...要求 n! = 1*2*3...*n ...易看出在k的倍数里..有1个k..在k的平方的有2个k..在k的立方中有3个k... 那么 n!  中k的个数为  n/k+n/(k^2)+n/(n^3)....及为最大的 i ...
     拓展一步..若k非质数..但只有一个质因子..如8,9,125 之类的...可以先求出在 n! 中有多少个其质因子,设为x...那么有多少个k..就是 i = x/p...p是指k为起质因数的多少次方..
     最终拓展出题目所要求的任意数的情况..k=a1^k1 * a2^k2 * a3^k3...an^kn  其中a1,a2...an为质数..可以算出n!中有多少a1,a2,a3...an...而组成一个k需要k1个a1..k2个a2..kn个an..那么也就是说n(a1)/k1 , n(a2)/k2 .... n(an)/kn...中最小的就是答案...

Program:
[cpp] 
#include<iostream> 
#include<stdio.h> 
#include<algorithm> 
#include<string.h> 
#include<math.h> 
#include<map> 
#include<queue> 
#include<stack> 
#define ll unsigned long long 
#define oo 1000000000 
#define pi acos(-1) 
using namespace std;     
ll t,n,i,k,temp,m,ans,p[80000],a[105],b[105],num,g; 
bool f[1000005]; 
int main() 
{  
     freopen("input.txt","r",stdin); 
     freopen("output.txt","w",stdout); 
     memset(f,true,sizeof(f)); 
     for (t=2;t<=1000000;t++) 
       if (f[t]) 
          for (k=t*2;k<=1000000;k+=t) f[k]=false; 
     m=0; 
     for (t=2;t<=1000000;t++) 
        if (f[t]) p[++m]=t; 
     cin>>t; 
     while (t--) 
     {    
           cin>>n>>k; 
           ans=0; 
           num=0; 
           temp=k; 
           for (i=1;i<=m;i++) 
              if (temp%p[i]==0)  
              { 
                     a[++num]=p[i];  
                     b[num]=0; 
                     while (temp%p[i]==0)  
                     { 
                            temp/=p[i]; 
                            b[num]++; 
                     }  
              } 
           if (temp!=1)  
           { 
                a[++num]=temp;  
                b[num]=1; 
           } 
           ans=(ll)(1e+18); 
           for (i=1;i<=num;i++) 
           { 
                temp=0; 
                g=a[i]; 
                while (1) 
                {                        
                       temp+=n/g; 
                       if (n/a[i]>=g) g*=a[i]; 
                          else break; 
                } 
                temp/=b[i];  
                ans=min(temp,ans); 
           }   
           cout<<ans<<endl; 
     } 
     return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,