http://162.105.81.212/JudgeOnline/problem?id=2992

?

题意：求组合数C[n][k]的约数个数。（０<= k <= n<= 431)

思路：一个数num的约数个数为cnt,将num质因数分解，得num = p1^a1 * p2^a2 * p3^a3 *……*pn^an.

则约数个数cnt = (a1 + 1) * (a2 + 1) * (a3 + 1) * ……　*(an + 1).

C[n][k] = n ! / ((n - k) ! * k !).

先预求1到４３１的素数表。没有预处理很容易超时的。

1.约数个数定理：设n的标准质因数分解为n=p1^a1*p2^a2*...*pm^am,
则n的因数个数=(a1+1)*(a2+1)*...*(am+1).
2.n!的素因子 = (n-1)!的素因子 + n的素因子
3.c(n,k)的素因子分解 = n!的素因子- (n-k)!的素因子 - k!的素因子

#include<iostream> using namespace std; const int maxn = 432; int res[maxn][maxn]; //n! 的素因子分解； bool s[maxn]; int sumprime, prime[maxn]; /*int p[83]={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, 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197, 199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313, 317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431}; 打表250ms*/ void Prime()//求素数 172ms. { int i,k,t; for (i=2;i<=435;i+=2) { s[i]=0; s[i-1]=1; } s[1]=0; s[2]=1; for (i=3;i<=30;i+=2) { if (s[i]) { k=2*i; t=i+k; while (t<=435) { s[t]=0; t=t+k; } } } k=0; prime[0]=2; for (i=3;i<=435;i+=2) { if (s[i]==1) { k++; prime[k]=i; } } sumprime=k; //for(i=0; i<sumprime; i++) // printf("%d ",prime[i]); } void fun() //整数分解 n!=p1^t1*…*pk^tk 求n!的素因子分解 { int i, j, temp; for(i=2; i<=431; i++) { //for(j=0; j<=i; j++) // res[i][j] = res[i-1][j]; temp = i; for(j=0; j<sumprime; j++) { while(temp>1 && temp % prime[j] == 0) { res[i][j]++; //素因子数++； temp /= prime[j]; } } } for(i=3; i<=431; i++) for(j=0; j<sumprime; j++) res[i][j] += res[i-1][j]; } int main() { int k, n, i; __int64 ans; Prime(); fun(); while(scanf("%d%d",&n,&k) !=EOF) { ans = 1; for(i=0; i<sumprime; i++) //n的因数个数=(a1+1)*(a2+1)*...*(am+1). ans *= (1 + (res[n][i] - res[k][i] - res[n-k][i])); printf("%I64d/n",ans); } return 0; }?

?