题目描述
求出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
这道题我第一次看顿时就觉得变态至极，这不就是高精乘然后高精除以高精吗？！然后磨蹭了半天最后还是跪在高精除以高精了…………
最后看了下标程……………………
差点吐血…………………………
咳咳，首先这道题是组合数，那也就是说一定能整除，那我们能不能先去约分？这样就说不定避免了高精除了。
约分这回事，标程非常妙。首先他将分子全部分解质因数，然后将分母也不断分解质因数，分母分解的同时就可以用他的质因数来约分了。这样分母分解完后，剩下的质因数就全部是答案的了。
再具体讲一下，首先开一个数组a，记录质因数，a[i] 代表的就是质因数 i 的个数。因为 n <= 30000，所以 a 开30000就足够了。
对于分子，找到一个质因数 i 就 a[i]++。而且因为分子是一堆数的乘积，所以将每一个乘数分解就行，不要都乘起来再分解，那肯定会爆 long long。
对于分母，也是同理，只不过找到一个 i 就 a[i]--，这就相当于约分了，妙。
最后a数组中非0的 a[i] 的就是答案的质因数了。
不过还要说一下答案。理论上把 a 数组中剩下的都乘起来就行了（高精乘），但是别忘了我们只用输出后十位，所以保守一点算出后20位就行了，到了20就停。这样就大大节省了时间，而且存答案的数组只用开到21就足够了。
1 #include <iostream> 2 #include <cstring> 3 #include<algorithm> 4 #include <cstdio> 5 #include <cmath> 6 using namespace std; 7 const int max_size = 3e4 + 5; 8 const int maxn = 20; 9 int a[max_size], b[maxn + 5]; 10 int n, r; 11 void divide(int n) //约分 12 { 13 for(int m = 2; m * m <= n; ++m) 14 { 15 while (n % m == 0 && n!= 0) 16 { 17 n /= m; 18 a[m]--; 19 } 20 } 21 a[n]--; 22 } 23 void fenjie(int n) //a[]记录分子质因数 24 { 25 for(int m = 2; m * m <= n; ++m) 26 { 27 while(n % m == 0 && n != 0) 28 { 29 n /= m; 30 a[m]++; 31 } 32 } 33 a[n]++; 34 } 35 void multi(int d) //只是算出后20位的高精乘 36 { 37 int jinwei = 0; 38 for(int i = 1; i <= maxn; ++i) 39 { 40 b[i] = b[i] * d + jinwei; 41 jinwei = b[i] / 10; 42 b[i] %= 10; 43 } 44 } 45 int main() 46 { 47 scanf("%d%d", &n, &r); 48 for(int i = n - r + 1; i <= n; ++i) fenjie(i); //将分子分解质因数 49 for(int j = r; j > 1; --j) divide(j); //不断约分 50 b[1] = 1; 51 for (int i = 2; i <= 29999; ++i) //在a[]里剩的就是得数的所有质因子了，所以只要都乘起来就行了 52 { //高精乘 53 while (a[i] > 0) 54 { 55 multi(i); 56 a[i]--; 57 } 58 } 59 for(int i = 10; i >= 1; --i) printf("%d", b[i]); 60 printf(" "); 61 return 0; 62 }
妙，真的妙