求C(n,k)的因子个数
C(n,k) = (n*(n-1)*...*(n-k+1))/(1*2*...*k) = p1^k1 * p2^k2 * ... * pt^kt
这里只要计算出分子中素数因子个数减去分母中的个数
然后每一种因子都有 (cnt+1)种取的可能，乘一下就出来了
但是不能逐个因子分解，试了两次都错了，后来初始的时候，先将这432个数提前预处理分解好保存到vector中
然后用的时候直接提取就行
不然会因为数据量太大超时的
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <ctime> 6 #include <cstdlib> 7 #include <vector> 8 9 using namespace std; 10 #define ll long long 11 #define N 500 12 #define pii pair<int,int> 13 int cnt[N+5] , prime[N+5] , tot; 14 bool check[N+5]; 15 vector<pii> v[N]; 16 17 void init() 18 { 19 check[1] = true; 20 for(int i=2 ; i<=N ; i++) 21 { 22 if(!check[i]) prime[tot++] = i; 23 for(int j=i+i ; j<=N ; j+=i) check[j]=true; 24 } 25 } 26 27 void fenjie(int x) 28 { 29 int tmp = x; 30 for(int i=0 ; i<tot ; i++){ 31 if(prime[i]>x) break; 32 int cnt = 0; 33 while(x%prime[i]==0){ 34 x/=prime[i]; 35 cnt++; 36 } 37 if(cnt) v[tmp].push_back(make_pair(prime[i] , cnt)); 38 } 39 if(x>1) v[tmp].push_back(make_pair(x , 1)); 40 } 41 42 void solve(int n , int k) 43 { 44 memset(cnt , 0 , sizeof(int)*(n+1)); 45 for(int i=1 , up=n , dn=1 ; i<=k ; i++ , up-- , dn++){ 46 int l1 = v[up].size() , l2 = v[dn].size(); 47 for(int i=0 ; i<l1 ; i++) cnt[v[up][i].first] += v[up][i].second; 48 for(int i=0 ; i<l2 ; i++) cnt[v[dn][i].first] -= v[dn][i].second; 49 } 50 ll ret = 1; 51 for(int i=0 ; i<tot ; i++){ 52 if(prime[i]>n) break; 53 ret *= (cnt[prime[i]]+1); 54 } 55 printf("%I64d " , ret); 56 } 57 58 int main() { 59 // freopen("a.in" , "r" , stdin); 60 // freopen("out.txt" , "w" , stdout); 61 init(); 62 for(int i=1 ; i<=432 ; i++) {v[i].clear();fenjie(i);} 63 int n , k; 64 while(~scanf("%d%d" , &n , &k)){ 65 solve(n , k); 66 } 67 }