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;
}
啟發(fā)：申請數(shù)組一定要大一號a[200001]，否則無法清空a[200000];
發(fā)現(xiàn)遞推規(guī)律要從特點和出發(fā)，乘法自然是乘法。
posted on 2009-06-30 10:49
luis 閱讀(227)
評論(0) 編輯 收藏 引用 所屬分類:
規(guī)律