挺有难题的一个排列组合（机试题）
下午去机试卷，碰到这么个题 大家瞧瞧有啥好点子。

数学中的 排列组合 Cm(下标)n（上标） = m！/(n! * (m-n)!) 1<n<m<100;

结果和过程都会遇到天文数字，64位的变量都可能不够用了。设计个函数，输入m，n值，输出结果。


[解决办法]
#include <iostream>
using namespace std;

void cmn(int m, int n, int *r, int len_r)
{
for(int i=0; i<len_r-1; ++i)
{
r[i] = 0;
}
r[len_r-1] = 1;

if(m<=n)
{
return;
}

int prim[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int prim_a[25] = {0};
int prim_b[25] = {0};

for(i=n+1; i<=m; ++i)
{
int i_temp = i;
for(int j=0; i_temp>1; ++j)
{
while(i_temp%prim[j]==0)
{
i_temp /= prim[j];
++prim_a[j];
}
}
}

for(i=2; i<=m-n; ++i)
{
int i_temp = i;
for(int j=0; i_temp>1; ++j)
{
while(i_temp%prim[j]==0)
{
i_temp /= prim[j];
++prim_b[j];
}
}
}

for(i=0; i<25; ++i)
{
prim_a[i] -= prim_b[i];
}
for(i=0; i<25; ++i)
{
int sum = 1;
while(prim_a[i]-->0)
{
sum *= prim[i];
}
prim_a[i] = sum;
}

for(i=0; i<25; ++i)
{
if(prim_a[i]>1)
{
for(int j=0; j<len_r; ++j)
{
r[j] *= prim_a[i];
}
for(j=len_r-1; j>0; --j)
{
r[j-1] += r[j]/10;
r[j] %= 10;
}
}
}
}

int main()
{
int m = 100;
int n = 49;

int r[50];//数组r用于存储结果
int len_r = 50;//数组r的长度为50，多余的位数设为零
cmn(m, n, r, len_r);
for(int i=0; i<len_r; ++i)
{
cout<<r[i];
}
cout<<endl;

return 0;
}
[解决办法]
to:12楼，关于幂求模的部分，有log(n)的方法，比如2^10000 mod x，不用算10000，只需要计算log(10000)次即可，求质数的话可以用筛法，这两部分都改进后，整体效率会提高一些。不过也就是翻倍而已。主要还是第一步约分的想法比较重要。