Submission #490985

#	Time	Username	Problem	Language	Result	Execution time	Memory
490985		duchung	Toys (CEOI18_toy)	C++17	100 / 100	2932 ms	82088 KiB

toy

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

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