计算n个数的最小公倍数需要取模的情况

sunzhen · 2020-06-06 19:45:24 · 个人记录

n<=1e4

ai<=1e6

将结果对1e9+7取模

首先想到对两个两个数取最小公倍数，得到最小公倍数就取模防止溢出。
但是该方法有问题。
例如1000000，999999，999998这三个数的最小公倍数
两个两个数取最小公倍数
前两个数的gcd为1.所以最小公倍数为
999999000000,然后把它与999998取最小公倍数，由于gcd为2，所以最小公倍数
为999999000000*999998/2
但是为了防止溢出，在算完前两个数的最小公倍数后如果对mod取模后变成了999999000000%mod=998993007
然后这个数和999998的gcd为1，
于是又把998993007与999998相乘了，所以结果出错

999999000000*999998/2%mod=501010528
998993007*999998%mod=2021049
显然不对
那么正解是这样
对每个ai进行质因数分解
随后对每一个因子，取这些数中分解出来的的最高次幂，相乘，相乘的过程中取模。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=1000500;
#define int long long
ll ans[max_n]={1};
ll ans1[max_n]={1};
ll end1[max_n];
ll n,p=1e9+7;
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b)
{
    int x=gcd(a,b);
    return a*b%p*end1[x]%p;
}
void fun(int n,int p)
{
    ans[1]=1;
    for(int i=2;i<=n;i++)
    {
        ans[i]=(ans[i-1]*i)%p;
    }
}

ll pow(ll x,ll n,ll mod)
{
    if(n==0)return 1%mod;
    ll ans=1;
    while(n>0)
    {
        if(n&1)ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}

void fu(int n,int p)
{
    ans1[n]=pow(ans[n],p-2,p);
    for(int i=n-1;i>=1;i--)
    {
        ans1[i]=ans1[i+1]*(i+1)%p;
    }
}

void f(int n,int p)
{
    for(int i=n;i>=1;i--)
    {
        end1[i]=(ans1[i]*ans[i-1])%p;
    }
}
ll a[1000006];
ll LCM=1;
ll GCD;
int x;
ll endd;
ll cheng=1;
int mx[1000005];
signed main()
{
    n=1000005;
    fun(n,p);
    fu(n,p);
    f(n,p);
    int t;cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>a[i];
        int x=a[i];
        for(int v=2;v*v<=x;v++)
        {
            if(x%v)continue;
            int cur=0;
            while(x%v==0)
            {
                cur++;
                x/=v;
            }
            mx[v]=max(mx[v],cur);
        }
        if(x!=1)mx[x]=max(mx[x],1LL);
    }
    for(int i=2;i<=n;i++)
    {
        if(mx[i])
        {
            LCM=LCM*pow(i,mx[i],p)%p;
        }
    }
    cout<<LCM%p;
}