学步园

题目连接：http://acm.fzu.edu.cn/problem.php?pid=1607

思路：可以直接利用素数打表，然后分解质因数，计算因数的个数

最后个数-1就是答案，然后再枚举最小的因数就可以了

我的代码：

#include<stdio.h><br /> #include<string.h></p> <p>int prime[500000];<br /> int num=0;<br /> bool flag[1000005];</p> <p>void init()<br /> {<br /> __int64 i,j;<br /> memset(flag,0,sizeof(flag));<br /> flag[1]=true;<br /> flag[0]=true;<br /> for(i=2;i<1000005;i++)<br /> {<br /> if(!flag[i])<br /> {<br /> prime[num++]=(int)i;<br /> for(j=i*i;j<1000005;j=j+i)<br /> flag[j]=true;<br /> }<br /> }<br /> }</p> <p>void slove(int n)<br /> {<br /> int i,time,res=1,ans;<br /> int N=n;<br /> bool flag=true;<br /> for(i=0;prime[i]*prime[i]<=n;i++)<br /> {<br /> time=0;<br /> if(n%prime[i]==0)<br /> {<br /> n=n/prime[i];<br /> time++;<br /> while(n%prime[i]==0)<br /> {<br /> n=n/prime[i];<br /> time++;<br /> }<br /> res=res*(time+1);<br /> if(flag)<br /> {<br /> flag=false;<br /> ans=prime[i];<br /> }<br /> }<br /> if(n==1)<br /> break;<br /> }<br /> time=0;<br /> if(n>1)<br /> {<br /> time++;<br /> res=res*(time+1);<br /> if(flag)<br /> {<br /> flag=false;<br /> ans=n;<br /> }<br /> }<br /> printf("%d %d/n",res-1,N/ans);<br /> }</p> <p>int main()<br /> {<br /> int n;<br /> init();<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> if(!flag[n])<br /> {<br /> printf("1 1/n");<br /> continue;<br /> }<br /> slove(n);<br /> }<br /> return 0;<br /> }

还有一份代码，居然超时了。。很悲剧

#include<stdio.h><br /> #include<iostream><br /> #include<math.h></p> <p>using namespace std;</p> <p>bool isprime(int n)<br /> {<br /> int i;<br /> for(i=2;i*i<=n;i++)<br /> if(n%i==0)<br /> return false;<br /> return true;<br /> }</p> <p>int count(int n)<br /> {<br /> int i,m,ans=0;<br /> m=(int)sqrt((double)(n));<br /> for(i=1;i<=m;i++)<br /> ans=ans+n/i;<br /> return (ans<<1)-m*m;<br /> }</p> <p>int main()<br /> {<br /> int n,ans1,ans2,i;<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> if(isprime(n))<br /> {<br /> printf("1 1/n");<br /> continue;<br /> }<br /> ans1=count(n)-count(n-1);<br /> for(i=2;i<=n;i++)<br /> if(n%i==0)<br /> {<br /> ans2=n/i;<br /> break;<br /> }<br /> printf("%d %d/n",ans1-1,ans2);<br /> }<br /> return 0;<br /> }