Submission #490969

#TimeUsernameProblemLanguageResultExecution timeMemory
490969duchungToys (CEOI18_toy)C++17
79 / 100
5095 ms54064 KiB
#include<bits/stdc++.h>
using namespace std;

int n;
map<pair<int , int> , bool> visited;
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[{n , sum}] == true) return;
    visited[{n , sum}] = true;

    if (n == 1) 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);

    for (auto x : visited)
    {
        if (x.first.first == 1) ans.push_back(x.first.second);
        else break;
    }

    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...