ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - B Not-trivial Common Divisor

問題

問題概要

個の数が与えられます。
その中で、全ての要素がで割り切れるような集合を作り、そのの総和を最大化してください。

解法

を合成数にするよりも、素数にした方がお得(と選ぶと、が約数ではあるがが約数に含まれない数の分だけ損をしてしまう)なので、素因数についてのみ考えていけば良いです。
あとは、に含まれる素因数全てについて、それを約数としてもつの総和を計算し、最大値を求めればよいことになります。
素因数をキー、総和をvalueとするmapを作成し、について素因数分解を行いつつ加算していくと楽な気がします。
提出コードは以下になります↓

#include <bits/stdc++.h>
using namespace std;

long long n;
vector<long long> a;
map<long long,long long> mp;

long long solve();

int main(){
    cin >> n;
    a.resize(n);
    for(int i = 0;i < n;++i)cin >> a[i];
    cout << solve() << endl;
    return 0;
}

long long solve(){
    for(int i = 0;i < n;++i){
        long long x = a[i];
        for(long long j = 2;j * j <= a[i];++j)
            if(x % j == 0){
                while(x % j == 0)x /= j;
                mp[j] += a[i];
            }
        if(x > 1)mp[x] += a[i];
    }
    long long ans = 0;
    for(auto now : mp)ans = max(ans,now.second);
    return ans;
}