As you known,a positive integer can be written to a form of products of several positive integers(N = x1 * x2 * x3 *.....* xm (xi!=1 (1<=i<=m))).Now, given a positive integer, please tell me how many forms of products.
Input
Input consists of several test cases.Given a positive integer N (2<=N<=200000) in every case.
Output
For each case, you should output how many forms of the products.
Sample Input
12
100
5968
Sample Output
4
9
12
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
int a[200001];
freopen("s.txt","r",stdin);
freopen("key.txt","w",stdout);
int i,j,n;
memset(a,0,sizeof(a));
a[1]=1;
for(i=1;i<=200000;i++)
for(j=1;i*j<=200000;j++)
a[i*j]+=a[j];
while(scanf("%d",&n)!=EOF)
printf("%d\n",a[n]/2);
//system("PAUSE");
return 0;
}
启发：申请数组一定要大一号a[200001]，否则无法清空a[200000];
发现递推规律要从特点和出发，乘法自然是乘法。
posted on 2009-06-30 10:49
luis 阅读(195)
评论(0) 编辑 收藏 引用 所属分类:
规律