组合数的末十位

1129: 高精度组合数的末十位

题目描述

求出C(n,r)的最后十位，其中0<r≤n≤30000，输出时不足十位数也按十位输出，此时高位用0表示。C(n,r)=n×(n-1)×……×(n-r+1)/(1×2×3×……×r)。

输入数据为两个以空格隔开的自然数n，r。

输入

一行两个整数

输出

一行，10位数字

样例输入

5 2

样例输出

0000000010

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 using namespace std;
 7 int a[30000],t,i,j,n,r,s;
 8 int b[21]; 
 9 const int maxn=20;
10 void divide(int n)
11 {
12     int m;
13     m=2;
14     while (m*m<=n) 
15     {
16         while (n%m==0&&n!=0) 
17         {
18             n=n/m;
19             a[m]--;
20         }
21         m++;
22     }
23     a[n]--;                    //进行因数约分 
24 }
25  
26 void times(int n)  
27 {
28     int m;
29     m=2;              
30     while (m*m<=n)
31     {
32         while(n%m==0&&n!=0)
33         {
34             n=n/m;
35             a[m]++;
36         }
37         m++;
38     }
39     a[n]++;      //求出各个因数大小方便约分 
40 }
41  
42 void add(int d)
43 {
44     int dd,i,t;
45     i=1; j=0;     
46     while (i<=maxn)     //求十位保险起见求出二十位 高精度乘法 
47     {
48         t=b[i]*d+j;     
49         b[i]=t%10;
50         j=t/10;
51         i++;
52     }
53 
54 }
55  
56 int main()
57 {
58     cin>>n>>r;
59     memset(a,0,sizeof(a));
60     i=n-r+1;
61     j=r;    //循环的开始点 
62     do
63     {
64         if (i<=n)
65         {
66             times(i); i++;    //将这一段里面的因数划分出来求个数 
67         }
68         if (j>1)
69         {
70             divide(j); j--;  // 分子的各个因数个数减去分母中各个因数的个数 
71         }
72     }while(i<=n||j>1);
73      
74     memset(b,0,sizeof(b));
75     b[1]=1;
76     for (i=2;i<=29999;i++)
77     {
78         while (a[i]>0)  //只要有因数剩余则该因数相乘 
79         {
80             add(i);
81             a[i]--;   //把所有相同的因数乘一遍 
82         }
83     }
84     for (j=10; j>=1;j--)
85     cout<<b[j];    //输出十位 
86     cout<<endl;
87     return 0;
88 }

题解

1. 求出各个数的因数及该因数出现的次数

2. 进行约分

3. 将剩余的所有因数用高精度乘法乘

4. 将积只输出后十位。