呼兰河传(数学lcm)

呼兰河传(数学&lcm)

传送门

求$n$个数的最小公倍数$lcm$。

进行质因数分解，每个质因数去最大指数相乘即可。

时间复杂度:$O(nlogn)$

#include
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+9;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair
#define fi first 
#define se second
int cnt[N];
ll ksm(ll a,ll n){ll ans=1;while(n){if(n&1) ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);for(int j=2;j*j<=x;j++){if(x%j==0){int y=0;while(x%j==0) y++,x/=j;cnt[j]=max(cnt[j],y);}}if(x!=1) cnt[x]=max(cnt[x],1);}ll ans=1;for(int i=1;i<=1e5;i++)ans=ans*ksm(i,cnt[i])%mod;printf("%lld\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！