題目大意：判斷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 閱讀(485)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：數學/數論