UVa 10780 - Again Prime? No Time.(唯一分解)

输入 n 、 m ,求最大 k 使 ( m k ) % n = 0 。首先筛选出所有素数,然后求出所有 n
,唯一分解的结果。对于 m 进行分解,对于每一个在 m 中的素数 p [ i ] 的指数 e [ i ] , k = m
i n ( e [ i ] ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
int p[maxn],pnum,en[maxn][1250],em[maxn];
bool np[maxn]={1,1};
void init(){
for(int i=2;i<maxn;++i)
if(!np[i]){
p[pnum++]=i;
for(int j=i*i;j<maxn;j+=i)
np[j]=true;
}
for(int i=2;i<maxn;++i){
int k=i;
for(int j=0;j<pnum;++j){
while(k%p[j]==0) k/=p[j],++en[i][j];
en[i][j]+=en[i-1][j];
}
}
return;
}
int main(){
init();
int t,tt=0;scanf("%d",&t);
while(t--){
memset(em,0,sizeof em);
int m,n;scanf("%d%d",&m,&n);
int ans=0x3f3f3f3f;
for(int i=0;i<pnum;++i){
while(m%p[i]==0) m/=p[i],++em[i];
if(em[i]) ans=min(en[n][i]/em[i],ans);
}
printf("Case %d:\n",++tt);
if(ans) printf("%d\n",ans);
else puts("Impossible to divide");
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包