题目地址：

pid=5407">HDU 5407

题意：CRB有n颗不同的糖果，如今他要吃掉k颗(0<=k<=n)，问k取0~n的方案数的最小公倍数是多少。

思路：首先做这道题我们须要必备的几个技能点。

1. LCM(C(n,0), C(n,1),…, C(n,n))=LCM(1,2,3,…n+1)/(n+1)。额，这个有一篇证明Kummer定理

2.(1) 乘法逆元定义：

满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元(a,p互质)。

(2)为什么要用乘法逆元：

当我们要求（a/b） mod p的值，且a非常大，无法直接求得a/b的值时，我们就要用到乘法逆元。我们能够通过求b关于p的乘法逆元k，将a乘上k再模p。即(a*k) mod p。其结果与(a/b) mod p等价。

(3)乘法逆元的解法：

A：逆元能够用扩展欧几里德来解最小的正整数就可以:

a*x%p = 1;

a*x = y*p + 1;

a*x -p*y = 1;

B：当p是质数的时候 a/x mod p=a*x^(p-2) mod p

证明：若 a*b mod p = 1 则a和b互为乘法逆元。

由于p是质数。所以由费马小定理得出x^(p-1) mod p = 1 ，所以x*x^(p-2) mod p = 1是成立的，所以x 和 x^(p-2) 互为乘法逆元。

当p不是质数的时候a/x mod p=a*x^(phi(p)-1) mod p。

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

#include <bitset>

#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long  LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-7;

const int Maxn=1e6+10;

const int mod=1000000007;

bitset<Maxn>pri;

int prime[Maxn];

int vis[Maxn];

int k;

LL x;

LL f[Maxn];

void is_prime()

{

    pri.set();

    for(int i=2;i<Maxn;i++){

        if(pri[i]){

            prime[k++]=i;

            for(int j=i+i;j<Maxn;j+=i)

                pri[j]=0;

        }

    }

}

LL Mul(LL a,LL b,LL mod)

{

    LL res=0;

    while(b>0) {

        if(b&1)

            res=(res+a)%mod;

        b>>=1;

        a=(a+a)%mod;

    }

    return res;

}

LL modxp(LL a,LL b,LL mod)

{

    LL res=1;

    while(b>0) {

        if(b&1)

            res=Mul(res,a,mod);

        b>>=1;

        a=Mul(a,a,mod);

    }

    return res;

}

void get()

{

    memset(vis,0,sizeof(vis));

    for(int i=0;i<k;i++){//将素数p的k次方p^k标记一下，找出符合的素数

        x=prime[i];

        while(x<Maxn){

            vis[x]=prime[i];

            x*=prime[i];

        }

    }

    f[1]=1;

    for(int i=2;i<Maxn;i++){

        if(vis[i])

            f[i]=(f[i-1]*vis[i])%mod;

        else

            f[i]=f[i-1]%mod;

    }

}

int main()

{

    int T,n;

    is_prime();

    get();

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        printf("%lld\n",f[n+1]*modxp(n+1,mod-2,mod)%mod);//(f(n+1)/(n+1))%mod

    }

    return 0;

}