问题 A: 组合数

时间限制: 1 Sec 内存限制: 128 MB
提交: 1975 解决: 150
[提交] [状态] [命题人:jsu_admin]

题目描述

求组合数C(N,M)，以及C(N,M)因子个数。

输入

N和M，其中0<=M<=N<=50,以EOF结束。

输出

该组合数结果

样例输入 Copy

3 2
4 2

样例输出 Copy

3 2
6 4

因为求组合数的时候 long long 存不下，所以我们需要分解质因数再求解，它的就是把分子分母约去同时有的素因子以达到中间算阶乘的时候不会爆 long long


计算因子数用到了唯一分解定理
一个数 n 肯定能被分解成 n=p1^r1 * p2^r2 . . .*pn^rn
假设 p1p2,…pn 是它的素因子
假设 r1,r2,…rn 分别是 p1…pn 的幂次数
那么（1+r1）*（1+r2）….*(1+rn)就是他的因子数

  1 /**
  2 /*两个板子 快速幂+组合数
  3 */
  4 #include<stdio.h>
  5 #include <iostream>
  6 #include <bits/stdc++.h>
  7 #define maxn 200005
  8 typedef long long ll;
  9 using namespace std;
 10 const ll mod=998244353;
 11 ll fac[maxn],inv[maxn];
 12 ll pow_mod(ll a,ll n)
 13 {
 14     ll ret =1;
 15     while(n)
 16     {
 17         if(n&1) ret=ret*a%mod;
 18           a=a*a%mod;
 19           n>>=1;
 20     }
 21     return ret;
 22 }
 23 void init()
 24 {
 25     fac[0]=1;
 26     for(int i=1;i<maxn;i++)
 27     {
 28         fac[i]=fac[i-1]*i%mod;
 29     }
 30 }
 31 ll Cc(ll x, ll y)
 32 {
 33     return fac[x]*pow_mod(fac[y]*fac[x-y]%mod,mod-2)%mod;
 34 }
 35 //ll pow(ll x,ll n)
 36 //{
 37 //ll temp(x),res(1);
 38 //while(n)
 39 //{
 40 //if(n&1) 
 41 //{
 42 //res *= temp;
 43 //}
 44 //temp *= temp;
 45 //n>>=1;
 46 //}
 47 //return res;
 48 //}
 49 
 50 long long C[1000][1000];
 51 ll D(ll m,ll n)
 52 {
 53     for(int i=1;i<50;++i)
 54     {
 55         C[i][i]=1;
 56         C[i][0]=1;
 57     }
 58     for(int i=1;i<50;++i)
 59     {
 60         for(int j=i+1;j<50;++j)
 61         {
 62             C[j][i]=C[j-1][i-1]+C[j-1][i];
 63         }
 64     }
 65    // int m,n;
 66 //    while(cin>>m>>n)///C(m,n)
 67 //    {
 68 //        cout<<C[m][n]<<endl;
 69 //    }
 70     return C[m][n];
 71 }
 72 #define N 440
 73 int prime[N];
 74 bool vis[N];
 75 double fact(int n)//求阶乘
 76 {
 77 int i;
 78 double sum;
 79 sum=1;
 80 for(i=1;i<=n;i++)
 81 {
 82 sum=sum*i;
 83 }
 84 return sum;
 85 } 
 86 
 87 
 88 int Prime()
 89 {
 90     int cnt = 0;
 91     for (int i = 2; i <= N; ++i)
 92     {
 93         if (!vis[i])
 94         {
 95             prime[cnt++] = i;
 96         }
 97         for (int j = 0; j < cnt&&i*prime[j] <= N; ++j)
 98         {
 99             vis[i*prime[j]] = 1;
100             if (i%prime[j] == 0)break;
101         }
102     }
103     return cnt;
104 }
105 int num[500];
106 int Fcnt;
107 void solve(int n,int y)
108 {
109     for (int i = 0; i < Fcnt; ++i)
110     {
111         int c = 0, p = prime[i];
112         while (n / p )
113         {
114             c += n / p;
115             p *= prime[i];
116         }
117         num[i] = num[i] + y*c;
118     }
119 }
120 
121 //int main()
122 //{
123 //    Fcnt=Prime();
124 //    int n, m;
125 //    while (scanf("%d%d", &n, &m) != EOF){
126 //        memset(num, 0, sizeof(num));
127 //        solve(n, 1);
128 //        solve(m, -1);
129 //        solve(n - m, -1);
130 //        ll ans = 1;
131 //        for (int i = 0; i < Fcnt; ++i)
132 //        {
133 //            ans *= (num[i] + 1);
134 //        }
135 //        printf("%lld
", ans);
136 //    }
137 //}
138 int main(){
139     ll p,q,k,a,b;
140         Fcnt=Prime();
141 int n,m;
142 double n1,m1,o1;
143 double fact(int n);
144     while(scanf("%lld%lld%lld%lld%lld",&p,&q,&n,&m,&b)!=EOF){
145             printf("%lld
",p);
146     n1=fact(n);
147 m1=fact(m);
148 o1=fact(n-m);
149 int k = 0;
150  memset(num, 0, sizeof(num));
151         solve(n, 1);
152         solve(m, -1);
153         solve(n - m, -1);
154         ll ans = 1;
155 for(int i = 1;i*i<=((int)(n1/(m1*o1)));i++){
156     if((int)(n1/(m1*o1))%i==0)
157     k++;
158 } 
159 printf("%.0f ",n1/(m1*o1),k);
160 
161 //    ll CC = (long long)D(k,a); 
162     ll aa = (long long)pow(q,m);
163     ll bb = (long long)pow(p,b);
164     ll sum = ((long long)(n1/(m1*o1)))*aa*bb;
165 //    printf("%lld
",CC);
166     printf("%lld
",p);
167     printf("%lld
",sum);
168 }
169 }

View Code