HDU 5407 CRB and Candies(LCM +最大素因子求逆元)

【题目链接】

【题目大意】求LCM(Cn0,Cn1,Cn2....Cnn)%MOD 的值

【思路】来图更直观：

这个究竟是怎样推出的。说实话。本人数学归纳大法没有推出来，幸得一个大神给定愿文具体证明。点击这里：click here~~

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;

const int MOD=1e9+7;

typedef long long LL;

LL p[N];

LL arr[N];

bool ok(int n) //推断n是不是仅仅有一个质因子。p[n]表示n最大的质因子。

{

    int t=p[n];

    while(n%t==0&&n>1) n/=t;

    return n==1;

}

LL poww(LL a,LL b)

{

    LL res=a,ans=1;

    while(b)

    {

        if(b&1) ans=res*ans%MOD;

        res=res*res%MOD;

        b>>=1;

    }

    return ans;

}

LL niyuan(LL a) /// 求逆元

{

    return poww(a,MOD-2);

}

inline LL read()

{

    int c=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    return c*f;

}

void init()

{

    for(int i=1; i<N; ++i) p[i]=i;

    for(int i=2; i<N; ++i) if(p[i]==i)

    {

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

            p[j]=i;

    }

    arr[0]=1;

    for(int i=1; i<N; ++i)//求LCM

    {

        if(ok(i))

            arr[i]=arr[i-1]*p[i]%MOD;

        else arr[i]=arr[i-1];

    }

}

int main()

{

   init();

   int t;t=read();

   while(t--)

   {

       int n;n=read();

       LL ans=arr[n+1]*niyuan(n+1)%MOD;//由欧拉定理a^(p-1) mod p = 1 p是质数 所以a的逆元是a^{p-2}

       printf("%lld\n",ans);

   } return 0;

}