Submission #490985

#TimeUsernameProblemLanguageResultExecution timeMemory
490985duchungToys (CEOI18_toy)C++17
100 / 100
2932 ms82088 KiB
#include<bits/stdc++.h>
using namespace std;

int n;
unordered_map<long long , bool> visited;
unordered_map<int , vector<int>> Div;
vector<int> ans;

void calc(int x)
{
    for (int i = 1 ; i * i <= x ; ++i)
    {
        if (x % i == 0)
        {
            if (i != 1) Div[x].push_back(i);
            if (i * i != x && x / i != 1) Div[x].push_back(x / i);
        }
    }
}

void build()
{
    for (int i = 1 ; i * i <= n ; ++i)
    {
        if (n % i == 0)
        {
            calc(i);
            if (i * i != n) calc(n / i);
        }
    }
}

void backtrack(int n , int sum)
{
    if (visited[1000000000LL * n + sum] == true) return;
    visited[1000000000LL * n + sum] = true;

    if (n == 1)
    {
        ans.push_back(sum);
        return;
    }

    for (int x : Div[n]) backtrack(n / x , sum + x - 1);
}

int main()
{
    // freopen(".inp","r",stdin);
    // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    build();
    backtrack(n , 0);

    sort(ans.begin() , ans.end());
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...