Codeforces：Dreamplay and LCM

Codeforces：Dreamplay and LCM

题目链接：http://codeforces.com/group/gRkn7bDfsN/contest/212150/problem/D

题目大意：求$LCM(C(n,0),C(n,1),C(n,2),...,C(n,k))$.

数论

由算数基本定理可设，$C(n,m)=prod prime_i^{a_{mi}}$.

令$b_i=max{a_{xi}|0 leqslant x leqslant k}$，则$[C(n,0),C(n,1),C(n,2),...,C(n,k)]=prod prime_i^{b_i}$.

由组合数的公式$C(n,m)=frac{n!}{(n-m)! imes m!}$可以得到$C(n,m)=C(n,m-1) imes frac{n-m+1}{m}$，即如果求得$C(n,m-1)$的分解式，那么$C(n,m)$的分解式可以很轻松得到，同理也可以得到$[C(n,0),C(n,1),C(n,2),...,C(n,k)]$的分解式.

因为可能会用到多次同一个数的分解式，故可先将$2$到$n$的分解式预处理成表以降低复杂度.

代码如下：

 1 #include <iostream>
 2 #include <cstring>
 3 #define Max(x,y) (x>y?x:y)
 4 #define Min(x,y) (x<y?x:y)
 5 #define N 1000005
 6 using namespace std;
 7 typedef long long ll;
 8 bool isp[N];
 9 ll n,k,res=1,p[N],ans[N],temp[N],m=1000000007,table[N][25],f[N];
10 ll prime(ll n){
11     ll k=0;
12     memset(isp,1,sizeof(isp));
13     isp[1]=0;
14     for(ll i=2;i<=n;++i){
15         if(isp[i]){f[i]=k;p[k++]=i;}
16         for(ll j=0;j<k&&i*p[j]<=n;++j){
17             isp[i*p[j]]=0;
18             if(i%p[j]==0)break;
19         }
20     }
21     return k;
22 }
23 void trans(ll x,ll t){
24     for(ll i=1;i<=table[x][0];++i){
25         ll idx=f[table[x][i]];
26         temp[idx]+=t;
27         ans[idx]=Max(temp[idx],ans[idx]);
28     }
29 }
30 ll mpow(ll x,ll n){
31     ll b=x,ans=1;
32     while(n){
33         if(n&1)ans=(ans*b)%m;
34         b=(b*b)%m;
35         n>>=1;
36     }
37     return ans;
38 }
39 void takeTable(ll x){
40     for(ll i=2;i<=x;++i){
41         ll t=i;
42         for(ll j=0;t!=1;++j){
43             while(t%p[j]==0&&t!=1){
44                 t/=p[j];
45                 table[i][++table[i][0]]=p[j];
46             }
47             if(isp[t]){//cut the branch
48                 table[i][++table[i][0]]=t;
49                 break;
50             }
51         }
52     }
53 }
54 int main(void){
55     std::ios::sync_with_stdio(false);
56     cin>>n>>k;
57     ll np=prime(n);
58     takeTable(n);
59     for(ll i=1;i<=Min(k,n/2);++i){
60         if((n-i+1)%i){
61             trans(i,-1);
62             trans(n-i+1,1);
63         }else trans((n-i+1)/i,1);
64     }
65     for(ll i=0;i<np;++i)
66         res=(res*mpow(p[i],ans[i]))%m;
67     cout<<res<<"
";
68 }