http://acm.hdu.edu.cn/showproblem.php?pid=1019
LCM 即各数各质因数的最大值, 搞个 map 乱弄一下就可以了.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned int ui;
- map<ui,ui> M;
- ll _pow(ui f,ui s){
- ll res=1;
- while(s){
- res*=f;
- s--;
- }
- return res;
- }
- bool np[100005];
- ui p[100005];
- int ptop=0;
- void init(){
- np[1]=1;
- for(int i=2;i<=100000;i++){
- if(np[i])
- ;
- else{
- p[ptop++]=i;
- for(int j=i+i;j<=100000;j+=i)
- np[j]=1;
- }
- }
- //cout<<ptop<<endl;
- }
- void fj(ui tmp){
- if(tmp<=1){
- return;
- }
- if(tmp<=3){
- M[tmp]++;
- return;
- }
- for(int i=0;i<ptop&&p[i]*p[i]<=tmp;i++){
- //cout<<"i="<<i<<endl;
- //cout<<"p[i]="<<p[i]<<endl;
- int cnt=0;
- while(tmp%p[i]==0){
- tmp/=p[i];
- cnt++;
- }
- if(cnt){
- M[p[i]]=max(M[p[i]],(ui)cnt);
- }
- }
- if(tmp!=1){
- M[tmp]=max(M[tmp],(ui)1);
- }
- return;
- }
- int main() {
- init();
- int t;
- scanf("%d",&t);
- while(t--) {
- int n;
- scanf("%d",&n);
- M.clear();
- while(n--){
- ui tmp;
- scanf("%u",&tmp);
- //cout<<tmp<<endl;
- fj(tmp);
- }
- ll ans=1;
- for(auto &mi:M){
- ans*=_pow(mi.first,mi.second);
- }
- cout<<ans<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-3029603.html