bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

PKU 2992
给出n跟k,求有多少个约数。
思路如下:
要知道一个数n约数的个数,首先要知道n的质因子分解:

                                 

接着就可以按下式来算所有约数的个数了:

                                 

其次,要知道一个数n的质因子分解,要打素数表,然后对每个小于n的素数p试除,看n含有多少个p的因子。

题目是要求n!/(k!(n-k)!的约数个数,如果直接算出n!/(k!(n-k)!会很麻烦,可以分别对n!, k!, (n-k)!做如上分解,然后对于同一个底,用n在的指数减去k对应的指数及(n-k)对应的指数,就得到n!/(k!(n-k)!在底的指数了。
可以用递推的方法来求n!的质因子分解,具体见代码。
 1 // pku 2992 质因子分解
 2 #include <iostream>
 3 #include <math.h>
 4 using namespace std;
 5 
 6 int p[90];        // 素数表
 7 int pn;
 8 int e[432][90];    // 对应素数的指数,质因子分解
 9 int n,k;
10 
11 // 筛法复杂度为O(n^2),下面的试除法只要sigma(sqrt(i)),2<=i<=n
12 void prime()
13 {
14     int i,j;
15     pn=0;
16     p[pn++]=2;
17     for(i=3;i<=431;i++){
18         int up=(int)sqrt(i);
19         int flag=0;
20         for(j=2;j<=up && !flag;j++){
21             if(i%j==0) flag=1;
22         }
23         if(flag==0) p[pn++]=i;
24     }
25     //printf("cnt=%d\n",pn);
26     //for(i=0;i<pn;i++) printf("%d ",p[i]);
27     return;
28 }
29 
30 void fact()
31 {
32     int i,j;
33     for(i=2;i<=431;i++){
34         int a=i;
35         //printf("%d:",a);
36         for(j=0;j<pn;j++){
37             while(a>1 && a%p[j]==0) {e[i][j]++;a/=p[j];}
38             //printf("%d ",e[i][j]);
39         }
40         //printf("\n");
41     }
42     for(i=3;i<=431;i++){
43         for(j=0;j<pn;j++) e[i][j]+=e[i-1][j];
44     }
45 }
46 
47 /*
48 void divide(int a)
49 {
50     int i;
51     for(i=0;i<pn;i++){
52         while(a%p[i]==0) {e[e]--;a/=p[i];}
53     }
54 }
55 */
56 
57 int main()
58 {
59     //freopen("in.txt","r",stdin);
60     int i,j;
61     prime();
62     fact();
63     while(scanf("%d%d",&n,&k)!=EOF){
64     //for(n=0;n<=431;n++){
65         //for(k=0;k<n;k++){
66             __int64 sum=1;
67             for(i=0;i<pn;i++) sum*=(1+(e[n][i]-e[k][i]-e[n-k][i]));
68             printf("%I64d\n",sum);
69         //}
70         //printf("1\n");
71     }
72     return 1;
73 }
posted on 2008-03-14 13:57 bon 阅读(289) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator