题目大意：判断n!能否被m整除（n、m都在longint范围内）。
将从1到n每个数字对m求最大公约数然后抵消，显然在n较大的时候效率不理想。
这道题想了很久，终于想到可以这么来做：对m分解质因数，求出每个因子pi出现的次数ei，然后计算因子pi在n!中出现了多少次（复杂度O(log(p,n))）。
以下是我的代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(10007);
int n,m;
int cnt,p[kMaxn],e[kMaxn];
void fac(int x)
{
cnt=0;
memset(e,0,kMaxn*sizeof(int));
if(!(x&1))
{
p[++cnt]=2;
while(!(x&1))
{
e[cnt]++;
x>>=1;
}
}
for(int i=3;i*i<=x;i+=2)
if(x%i==0)
{
p[++cnt]=i;
while(x%i==0)
{
e[cnt]++;
x/=i;
}
}
if(x!=1)
{
p[++cnt]=x;
e[cnt]++;
}
}
int f(int a,int b)
{
int re(0);
for(int i=a;i;i/=b)
re+=(i/b);
return re;
}
bool OK()
{
for(int i=1;i<=cnt;i++)
if(f(n,p[i])<e[i])
return false;
return true;
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
fac(m);
if(OK())
printf("%d divides %d!\n",m,n);
else
printf("%d does not divide %d!\n",m,n);
}
return 0;
}
posted on 2011-05-28 07:33
lee1r 阅读(455)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：数学/数论