#include using namespace std; long longestSequence(vector a) { map m; vector prime; long sum = 0; long Max = 0; for(auto ai : a){ if(ai==1) sum++; else{ if(m.count(ai)==0) m[ai]=0; m[ai]++; } Max = max(Max,ai); } if(Max<=1) return sum; long len = (long)sqrt(Max)+1000; vector pr(len+1,true); for(long i=2;i<=len;i++) if(pr[i]) for(long j=i*2;j<=len;j+=i) pr[j] = false; for(long i=2;i<=len;i++) if(pr[i]) prime.push_back(i); for(auto mi:m){ vector v; long key = mi.first; long sq = (long)sqrt(key); for(int pi=0;prime[pi]<=sq;pi++){ while(key>1 && key%prime[pi]==0){ v.push_back(prime[pi]); key/=prime[pi]; } if(key==1) break; } if(key>1) v.push_back(key); long p=1; long total = mi.first; for(int i=v.size()-1;i>=0;i--){ total += p; p *= v[i]; } sum += total*mi.second; /* cout<<"\nFOR:"<> n; vector a(n); for(int a_i = 0; a_i < n; a_i++){ cin >> a[a_i]; } long result = longestSequence(a); cout << result << endl; return 0; }