fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <iostream>
  8. #include <string>
  9. #include <set>
  10. #include <map>
  11.  
  12. using namespace std;
  13.  
  14. const int N=int(2e6)+2;
  15. bool is[N];
  16. int prv[N],d,n,a[200100];
  17. int ans[N];
  18. int s[1000],top,x,no,num[1000],so,mu,cur;
  19. pair<int,int> v[1000];
  20. long long kq=0LL;
  21.  
  22. int main(){
  23.     for(int i=4;i<N;i+=2){
  24.         is[i]=1;prv[i]=2;
  25.     }
  26.     for(int i=3;i<N;i+=2) if (!is[i]) for(d=i+i;d<N;d+=i){
  27.         if (!prv[d]) prv[d]=i;
  28.         is[d]=1;
  29.     }
  30.     scanf("%d",&n);
  31.     int i,j,k;
  32.     for(i=0;i<n;++i){
  33.         scanf("%d",&x);
  34.         if (x==1){continue;}
  35.         top=0;
  36.         while (x>1){
  37.             if (!is[x]){s[top++]=x;break;}
  38.             s[top++]=prv[x];
  39.             x/=prv[x];
  40.         }
  41.         sort(s,s+top);
  42.         no=0;
  43.         v[no++]=make_pair(s[0],1);
  44.         for(j=1;j<top;++j) if (s[j]!=s[j-1]) v[no++]=make_pair(s[j],1);
  45.         else v[no-1].second++;
  46.         so=cur=1;
  47.         num[0]=1;
  48.         for(j=0;j<no;++j){
  49.             cur=so;mu=1;
  50.             while (v[j].second--){
  51.                 mu*=v[j].first;
  52.                 for(k=0;k<cur;++k) num[k+so]=mu*num[k];
  53.                 so+=cur;
  54.             }
  55.             cur=so;
  56.         }
  57.         for(j=0;j<so;++j) ans[num[j]]++;
  58.     }
  59.     kq=1LL*n;
  60.     for(int i=1;i<N;++i) if (ans[i]>1) kq=max(kq,1LL*i*ans[i]);
  61.     cout<<kq;
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.12s 21728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kmrO5I
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!