赛后看这题题解仅仅有满眼的迷茫………………

g(N) = LCM(C(N,0),C(N,1),...,C(N,N))

 $f(n)=LCM(1,2,...,n)$, the fact $g(n)=f(n+1)/(n+1)$

f(n)\ =\ LCM(1, 2, ..., n)f(1) = 1

If n\ =p^{k}n =p​k​​ then $f(n)=f(n-1)\times p$, else $f(n)=f(n-1)$.

和不断的woc…… 后来QAQ巨找到了推导的文章。

。。

恩……贴上来……

感觉我有公式恐惧症。。

。

看到长串公式就犯晕= = 巨巨们研究研究吧…………

感觉依据题解能做出来已经非常好了

事实上这题另一点是要取余 因为须要取余 不能做除法 因此要求个分母的乘法逆元 刚好在攻数论的扩欧，扩欧小费马都能做 前一篇有扩欧的不错的帖子链接 有兴趣的能够去瞅瞅

本题代码例如以下:

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define sz 1000000#define ll long longconst int mod = 1e9+7;int p[sz+1];ll f[sz+1];bool ok(ll x){    int t = p[x];    while(x%t == 0 && x > 1) x /= t;    return x == 1;}void Init(){    int i,j;    for(i = 1; i <= sz; ++i) p[i] = i;    for(i = 2; i <= sz; ++i)        if(p[i] == i)            for(j = i+i; j <= sz; j += i)                if(p[j] == j) p[j] = i;    f[0] = 1;    for(i = 1; i <= sz; ++i)    {        if(ok(i)) f[i] = f[i-1]*p[i]%mod;        else f[i] = f[i-1];    }}//扩欧//int e_gcd(int a,int b,int &x,int &y)//{//    if(!b)//    {//        x = 1;//        y = 0;//        return a;//    }//    ll tmp = x,ans = e_gcd(b,a%b,x,y);//    tmp = x;//    x = y;//    y = tmp - a/b*y;//    return ans;//}ll pow(ll a,int m){    ll ans = 1;    for(;m; m >>= 1, a= a*a%mod)        if(m&1) ans = ans*a%mod;    return ans;}ll cal(int a,int m){//扩欧//    int x,y;//    int gcd = e_gcd(a,m,x,y);//    return (x/gcd+m)%m;//小费马    return pow(a,m-2);}int main(){    Init();    int t,n;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        printf("%lld\n",f[n+1]*cal(n+1,mod)%mod);    }    return 0;}