제출 #490975

#제출 시각아이디문제언어결과실행 시간메모리
490975duchungToys (CEOI18_toy)C++17
79 / 100
5056 ms80608 KiB
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n;
map<pair<int , int> , bool> visited;
vector<int> Div[N];
vector<int> ans;

void calc(int x)
{
    if (x > 1e6) return;

    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;

    if (n <= 1e6)
    {
        for (int x : Div[n]) backtrack(n / x , sum + x - 1);
    }
    else
    {
        for (int i = 1 ; i * i <= n ; ++i)
        {
            if (n % i == 0)
            {
                if (i != 1) backtrack(n / i , sum + i - 1);
                if (i * i != n && n / i != 1) backtrack(i , sum + n / i - 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...