Sum by Factors

• Time : $O(\sqrt{A_i} * log(factor(A_i)))$
• Space : $O(factor(A_i))$

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

class SumOfDivided
{
public:
    static std::string sumOfDivided(std::vector<int> &lst);
};
string SumOfDivided::sumOfDivided(std::vector<int> &lst) {
    map<int, long long> sum;
    for(auto x : lst) {
        int now = x;
        if(now < 0) now = -now;
        for(int i = 2; i * i <= now; i++) {
            if(now % i) continue;
            sum[i] += x;
            while(now % i == 0) now /= i;
        }
        if(now != 1) sum[now] += x;
    }
    string res = "";
    for(auto [k,v] : sum) res += "(" + to_string(k) + " " + to_string(v) + ")";
    return res;
}