学步园

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