uva10780 - Again Prime? No time

?

?

Again Prime? No time.

The problem statement is very easy. Given a number?n?you have to determine the largest power of?m, not necessarily prime, that divides?n!.

? ?

Input

The input file consists of several test cases. The first line in the file is the number of cases to handle. The following lines are the cases each of which contains two integers?m (1?and?n (0. The integers are separated by an space. There will be no invalid cases given and there are not more that?500?test cases.

Output

? ?

For each case in the input, print the case number and result in separate lines. The result is either an integer if?m?divides?n!?or a line "Impossible to divide" (without the quotes). Check the sample input and output format.

? ?

Sample Input

2
2 10
2 100

Sample Output

Case 1:
8
Case 2:
97

?

題目大意：給定m和n，求一個最大正整數k，使得m^k能夠被n!整除，變相問n！中有多少個m;

?

思路：開始想到的是從2-n遍歷，把每個數中有多少的m都找出來，后來發現缺陷是m不是質數，例如4*9和6，就找不出有6，實際上應該有兩個！正確的解法是分解質因數，然后找出有多少對質因數即可。當然要找的是對于每個質數的最小值.

code：#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int M=0x7fffffff;
const int N=10010;

bool ft[N];
int prime[N],t=0;
void init() //打素數表
{
memset(ft,true,sizeof(ft));
ft[0]=ft[1]=false;
for (int i=2;i<N;i++)
{
if (!ft[i]) continue;
prime[++t]=i;
for (int j=2*i;j<N;j+=i)
ft[j]=false;
}
}
int main()
{
init();
int T;
int m,n;
int i,j;
scanf("%d",&T);
for (int ca=1;ca<=T;ca++)
{
scanf("%d %d",&m,&n);
int ans=M,p=1;
while (m>1)
{
int ct=0;
while (m%prime[p]==0) //分解素數，從前往后找
{
ct++;
m/=prime[p];
}
if (ct==0){p++; continue;}
if (prime[p]>n){ans=-1; break;}
int nt=0;
for (i=prime[p];i<=n;i*=prime[p])
nt+=n/i;
ans=min(ans,nt/ct); //選出最小的素數比，也就是ans個素數對
}
printf("Case %d:\n",ca);
if (ans==-1) cout<<"Impossible to divide"<<endl;
else cout<<ans<<endl;
}

}
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的uva10780 - Again Prime? No time的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。