首页 > 代码库 > HDU 3988 n!质因数分解

HDU 3988 n!质因数分解

2024-07-17 21:00:52   236人阅读

Harry Potter and the Hide Story

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2324    Accepted Submission(s): 569


Problem Description
iSea is tired of writing the story of Harry Potter, so, lucky you, solving the following problem is enough.
 

 

Input
The first line contains a single integer T, indicating the number of test cases.
Each test case contains two integers, N and K. 

Technical Specification

1. 1 <= T <= 500
2. 1 <= K <= 1 000 000 000 000 00
3. 1 <= N <= 1 000 000 000 000 000 000
 

 

Output
For each test case, output the case number first, then the answer, if the answer is bigger than 9 223 372 036 854 775 807, output “inf” (without quote).
 

 

Sample Input
2
2 2
10 10
 

 

Sample Output
Case 1: 1
Case 2: 2
 
 
题意：
给两个数n和k，范围题中给出，然后求最大的 i 使得n！%(k^i)==0。
 
思路：
若想n!%(k^i)==0，那么k的质因数全部包含在n!中，那么找出k的质因数和n!的质因数，若两质因数相等，该质因数在k中含有b个，在n!中含有a个，那么算出a/b，对于所有不同的质因数算出a/b，那么最小的a/b就是所求的 i （木桶效应）。
 
代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <iostream> 6 using namespace std; 7 #define N 10000005 8  9 __int64 n, m;10 int p[N], tot;11 int vis[N];12 13 void init_p(){          //由于k最大为1<<15，那么初始化素数到1<<8就行了 14     int i, j;15     tot=0;16     for(i=2;i<N;i++){17         if(!vis[i]) p[tot++]=i;18         for(j=0;j<tot&&p[j]*i<N;j++){19             vis[p[j]*i]=1;20             if(i%p[j]==0) break;21         }22     }23 }24 25 __int64 nn(__int64 a,__int64 b){    //算出n!包含质因数b的个数 ，不懂请看《编程之美》第2.2 26     __int64 ans=0;27     while(a){28         a/=b;29         ans+=a;30     }31     return ans;32 }33 34 main()35 {36     __int64 a, b, MINH;37     init_p();38     int i, j, k, kase=1;39     int t;40     cin>>t;41     while(t--){42         scanf("%I64d %I64d",&n,&m);43         MINH=-1;44         if(m==1){45             printf("Case %d: inf\n",kase++);continue;46         }47         for(i=0;i<tot&&p[i]<=m;i++){48            b=0;49            if(m%p[i]!=0) continue;50             while(m%p[i]==0){51                 m/=p[i];52                 b++;53             }54             a=nn(n,p[i]);55             a/=b;56             if(MINH==-1) MINH=a;57             else MINH=min(MINH,a);58         }59         if(m>1){           //由于咱们需要把m全部包含到n!中，防止m还有剩余，所以有了这个函数 60             61             a=nn(n,m);//printf("1111111111\n");62             if(MINH==-1) MINH=a;63             else MINH=min(MINH,a);64         }65         printf("Case %d: %I64d\n",kase++,MINH);66     }67 }

 


联系
我们