学步园

题目连接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1095

刚刚看到这个题的数据规模的时候本来想用暴力，因为题目的数据量只有50w，但是很悲剧的TLE了

于是开始认认真真的想算法

可以很容易观察到，一个如下的规律

比如：20可以拆分为：2^2*5^1

那么就是1,2,4和1,5的组合相乘就是每一个因子

联想到牛顿二项式

得到：

(1+2+4)*(1+5)可以得到该答案为42,由于这个算式的和包括了一个特殊的因子，即该数n本身，于是我们必须将它减去就得到42-20=22

那么我们就可以很容易的写出程序来了（利用素数筛选法进行分解因式加速可以在500MS左右解决问题）

我的代码：

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