ATcoder E - Flatten 质因子分解求LCM

题解:其实就是求n个数的lcm，由于数据特别大，求lcm时只能用质因子分解的方法来求。

质因子分解求lcm。对n个数每个数都进行质因子分解，然后用一个数组记录某个质因子出现的最大次数。然后累乘pow(x,cnt)，即质因子x出现了cnt次。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=1E6+;

const ll mod=1e9+;

ll arr[N];

ll mp[N];

ll ksm(ll a,ll b){

    ll res=;

    while(b){

        if(b&) res=res*a%mod;

        a=a*a%mod;

        b>>=;

    }

    return res%mod;

}

int main()

{

    ios::sync_with_stdio(false );

    ll n;

    cin>>n;

    ll mx=;

    for(ll i=;i<=n;i++){

        cin>>arr[i];

        mx=max(mx,arr[i]);

    }

    ll pos=;

    for(ll i=;i<=n;i++){

        ll x=arr[i];

        ll y=sqrt(x);

        for(ll j=;j<=y;j++){

            ll cnt=;

            while(x%j==){

                x/=j;

                cnt++;

            }

            mp[j]=max(mp[j],cnt);

        }

        if(x!=) mp[x]=max(mp[x],(ll));

    }

    ll sum=;

    for(ll i=;i<=mx;i++)

        sum=(sum%mod*ksm(i,mp[i])%mod)%mod;

    ll ans=;

    for(ll i=;i<=n;i++){

        ans+=sum*ksm(arr[i],mod-)%mod;

    }

    cout<<ans%mod<<endl;

    return ;

}