CRB and Candies LCM 性质

题目 CRB and Candies
题意

\[ \text{给定正整数N，求} LCM \lbrace C \left(N , 0 \right),C\left(N , 1 \right),...,C\left(N , N \right) \rbrace \% mod \qquad 1\leq N \leq 10^6
\]

题解
- 根据规律推出公式，另外关于这个公式的证明
  
  \[ LCM \lbrace C \left(N , 0 \right),C\left(N , 1 \right),...,C\left(N , N \right) \rbrace \quad = \quad \frac{LCM(1,2,3...,N+1)}{N+1}
  \]
- 由于数据规模较大，除法取模可以化为求乘以N+1在模mod意义下的逆元再取模，问题就转化为了如何求连续自然数的LCM
- 由唯一分解定理可知LCM算法：
\[ X_1 = P_1^{e_1}*P_2^{e_2}*...*P_k^{e_k} \quad \\
X_2 = P_1^{e_1'}*P_2^{e_2'}*...*P_k^{e_k'} \quad \\
\text{$k$ $\to$ ∞ $\quad$ $P_i$ is a prime number} \\
\text{}\\
LCM(X_1,X2) = P_1^{max(e_1,e_1')} * P_2^{max(e_2,e_2')} *...* P_k^{max(e_k,e_k')}
\]
- 不妨设LCM[i]表示从1到i的lcm，则LCM[i+1]与LCM[i]的关系为

\[LCM \left[ i\right] =
\begin{cases}
LCM[i-1]*i\%mod, & \text{if $i$ is a prime number, because a new prime come in} \\[2ex]
LCM[i-1]*x\%mod, & \text{if $n$ is a POWER of prime number x, because $P_x$ get a high power }\\[2ex]
LCM[i-1], & \text{oherwise}
\end{cases}
\]

AC代码

#include<iostream>

#include<vector>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<string>

using namespace std;

typedef long long ll;

const int maxn = 1e6+10;

const ll mod = 1e9+7;

ll LCM[maxn];

bool isPrime[maxn];//isPrime[i]表示i是不是质数

int prime[maxn];//prime[i]表示i是哪个质数的k次幂 如果不是某个质数的k次幂就置0

void init(){

    for(int i=1; i<maxn; i++) isPrime[i] = 1, prime[i] = 0;

    isPrime[1] = 0;

    //素数普通筛 只需要筛到根号N即可

    for(int i=2; i*i<maxn; i++){

        if(isPrime[i]){

            ///cout<<i<<" ";

            for(int j=i*i; j<maxn; j *= i){

                prime[j] = i;//j 是 质数i的幂次

            }

            //筛素数

            for(int j=i+i; j<maxn; j += i){

                isPrime[j] = 0;

            }

        }

    }

}

//LCM[i]表示(1 , 2 , 3 ......, i)的lcm

void getLCM(){

    LCM[1] = 1;

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

        //如果是一个新质数

        if(isPrime[i]) LCM[i] = LCM[i-1] * i % mod;

        //如果不是质数 验证是不是一个质数的幂次

        //如果是 那么说明遇到了一个质因子更高的幂次  那么要多乘一个这个质因子

        else if(prime[i]) LCM[i] = LCM[i-1] * prime[i] % mod;

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

    }

}

//扩展欧几里得求逆元

void extgcd(ll a,ll b,ll& d,ll& x,ll& y){

    if(!b){ d=a; x=1; y=0;}

    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }

}

//返回a在模n意义下的逆元

ll inverse(ll a,ll n){

    ll d,x,y;

    extgcd(a,n,d,x,y);

    return d==1?(x+n)%n:-1;

}

int main(){

    int t;

    ll n;

    init();

    getLCM();

    cin>>t;

    while(t--){

        cin>>n;

        ll ans = LCM[n+1] * inverse(n+1 , mod) % mod;

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

CRB and Candies LCM 性质

最新文章

热门文章