제출 #490969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490969		duchung	Toys (CEOI18_toy)	C++17	79 / 100	5095 ms	54064 KiB

toy

#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 << " ";
}

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 21