题目链接：
?id=2992
题目大意：
求解出组合数C(n，k)的约数个数。
思路：
数据中的n和k值都比较大，，直接求解显然不可以。求约数个数，要先进行素因子分解。
C(n，k) = n!/(k!*(n-k)!)。n范围小于等于431，可以先筛选出431以内的素数，用数组Primer[]来存储素数。
分解，利用公式得到因子个数。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;bool Prime[500];int jie[500][90];__int64 zu[500][500];int Primer[500],num;void GetPrime(){for(int i = 2; i <= 431; ++i)Prime[i] = true;for(int i = 2; i <= 431; ++i){if(Prime[i]){for(int j = i+i; j <= 431; j+=i)Prime[j] = false;}}num = 0;for(int i = 0; i <= 431; ++i)if(Prime[i])Primer[num++] = i;}void solve(){//阶乘分解为 素因子相乘的形式jie[j][i]表示 j! 第i个素数的幂为多少for(int i = 0;i < num; ++i)for(int j = 2; j <= 431; ++j)jie[j][i] = j/Primer[i] + jie[j/Primer[i]][i];for(int i = 2; i <= 431; ++i) //计算因子个数{for(int j = 1; j < i; ++j){zu[i][j] = 1;for(int k = 0; k < num && jie[i][k]; ++k){int side = jie[i][k] – jie[j][k] – jie[i-j][k]; //计算C(i,j)中第i个素数的幂为多少if(side)zu[i][j] *= (side+1); //求因子个数}}}}int main(){GetPrime();solve();int n,m;while(~scanf("%d%d",&n,&m)){if(m==0 || m==n)printf("1\n");elseprintf("%I64d\n",zu[n][m]);}return 0;}
只有坚韧不拔向着目标奋进，成功后将在不远处等待着你的到来。
