学步园

题目连接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=13&problem=1080&mosmsg=Submission+received+with+ID+8769167

题意不解释了，直接说方法。

首先观察数据范围，loss than 2^31次方，所以一般的暴力算法肯定会超时的，故需要从阶乘的本质入手

首先是一个数论的基本常识：

n!中间包含了多少个x(x是任意的一个数，不过一般情况下我们都只讨论x为质数)，这种问题的答案是：
n/x+n/(x^2)+n/(x^3).....[一直加到x的乘方不超过n]，这个定理的证明也非常的简单，这里就不再赘述了

然后还有一个数论的基本常识就是任意一个数的质因数分解

必须知道这种分解是唯一的

即合数y=sigma[(pi)^ni]

而且pi的范围在2——sqrt(n)之间;

于是乎，我们可以先分解掉m（这个花不了多少时间，如果用质数筛选法加速的话）

然后我们再去看m分解出来的每一个pi在n!中是否有足够多，为了提速。我们可以先从最大的pi开始算

以下是我的代码：

#include<stdio.h><br /> #include<string.h></p> <p>struct node<br /> {<br /> long p;<br /> long n;<br /> node()<br /> {<br /> n=0;<br /> }<br /> };<br /> long prime[50000];<br /> bool flag[50000];<br /> node stc[1000];<br /> long num1=0,num2;</p> <p>void init()<br /> {<br /> unsigned long i,j;<br /> memset(flag,0,sizeof(flag));<br /> for(i=2;i<50000;i++)<br /> {<br /> if(!flag[i])<br /> {<br /> prime[num1++]=i;<br /> for(j=i*i;j<50000;j=j+i)<br /> flag[j]=true;<br /> }<br /> }<br /> }</p> <p>void devide(long m)<br /> {<br /> long i;<br /> num2=0;<br /> for(i=0;prime[i]*prime[i]<=m;i++)<br /> {<br /> if(m%prime[i]==0)<br /> {<br /> stc[num2].p=prime[i];<br /> stc[num2].n++;<br /> m=m/prime[i];<br /> while(m%prime[i]==0)<br /> {<br /> stc[num2].n++;<br /> m=m/prime[i];<br /> }<br /> num2++;<br /> }<br /> if(m==1)<br /> break;<br /> }<br /> if(m>1)<br /> {<br /> stc[num2].p=m;<br /> stc[num2].n++;<br /> num2++;<br /> }<br /> }</p> <p>bool judge(long n,long m)<br /> {<br /> long i,sum,temp;<br /> for(i=num2-1;i>=0;i--)<br /> {<br /> sum=0;<br /> temp=stc[i].p;<br /> while(n>=temp)<br /> {<br /> sum=sum+n/temp;<br /> temp=temp*stc[i].p;<br /> }<br /> if(sum<stc[i].n)<br /> return false;<br /> }<br /> return true;<br /> }</p> <p>int main()<br /> {<br /> long n,m,i;<br /> init();<br /> while(scanf("%ld%ld",&n,&m)!=EOF)<br /> {<br /> for(i=0;i<1000;i++)<br /> stc[i].n=0;<br /> if(n<=1&&m>1)<br /> {<br /> printf("%ld does not divide %ld!/n",m,n);<br /> continue;<br /> }<br /> if(m==0)<br /> {<br /> printf("%ld does not divide %ld!/n",m,n);<br /> continue;<br /> }<br /> if(n>=m)<br /> {<br /> printf("%ld divides %ld!/n",m,n);<br /> continue;<br /> }<br /> devide(m);<br /> if(judge(n,m))<br /> printf("%ld divides %ld!/n",m,n);<br /> else<br /> printf("%ld does not divide %ld!/n",m,n);<br /> }<br /> return 0;<br /> }