The problem can be found here

My Thought Process

The solution is quite straightforward. Since $c$ only goes up to $10^7$, we can just brute force it. We just precompute the sum of the divisors of all $n <= 10^7$. Then, we create an array with the minimum $n$ with the sum of its divisors being $x$ for $x <= 10^7$.

Implementation

The only thing a bit diffcult about this is implementing.

I first tried using binary search which quite obviously TLE.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

#define int long long

vector<int> s(1e7+1, 0);
vector<pair<int, int>> p;

void solve() { 
    int c; cin >> c;

    auto it = upper_bound(p.begin(), p.end(), make_pair(c-1, (ll)2e18));
    if((*it).first != c){
        cout << -1 << endl;
    }
    else{
        cout << (*it).second << endl;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int t;
    cin >> t;

    for(int i = 1; i <= 1e7; ++i){
        for(int j = i; j <= 1e7; j += i){
            s[j] += i;
        }
    }

    for(int i = 1; i <= 1e7; ++i){
        p.pb({s[i], i});
    }

    sort(p.begin(), p.end());
    while(t--){
        solve();
    }

    return 0;
}

Then, I just instead used an array which I probably should’ve tried first. It almost didn’t pass as it took 1859ms.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

vector<int> p(1e7+1, 0);
vector<int> d(1e7+1, 2e9);

void solve() { 
    int c; cin >> c;
    if(d[c] == 2e9){cout << -1 << endl;}
    else{cout << d[c] << endl;}
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int t;
    cin >> t;

    for(int i = 1; i <= 1e7; ++i){
        for(int j = i; j <= 1e7; j += i){
            p[j] += i;
        }
    }

    for(int i = 1e7; i >= 1; --i){
        if(p[i] <= 1e7){
            d[p[i]] = i;
        }
    }

    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.