POJ 2649 Factovisors（素因子分解）

因子分解）"/>

POJ 2649 Factovisors（素因子分解）

Description
给出两个整数n和m，判断m!是否能整除n
Input
多组用例，每组用例占一行包括两个整数n和m（均小于2^31)，以文件尾结束输入
Output
对于每组用例，判断m!是否能整除n
Sample Input
6 9
6 27
20 10000
20 100000
1000 1009
Sample Output
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!
Solution
阶乘的质因子分解，对于n的每个质因子p，首先求出n中p的幂指数a，然后对m!质因子分解求出m!中p对应的幂指数b，如果对于每个p均由b>=a则m!可以整除n，否则不行
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 55555
int prime[maxn],is_prime[maxn],res;
void get_prime()
{memset(is_prime,0,sizeof(is_prime));res=0;for(int i=2;i<maxn;i++)if(!is_prime[i]){prime[res++]=i;for(int j=i;j<maxn;j+=i)is_prime[j]=1;}
}
int check(int n,int p,int num)
{int ans=0;while(n){ans+=n/p;n/=p;}if(ans>=num)return 1;return 0;
}
int main()
{get_prime();int n,m;while(~scanf("%d%d",&n,&m)){int flag=1,tm=m;if(!m)flag=0;for(int i=0;flag&&i<res&&prime[i]<=m;i++)if(m%prime[i]==0){int num=0;while(m%prime[i]==0)num++,m/=prime[i];flag=check(n,prime[i],num);if(!flag)break;}if(flag&&m>1)flag=check(n,m,1);if(flag)printf("%d divides %d!\n",tm,n);else printf("%d does not divide %d!\n",tm,n);}return 0;
}