Submission #1092168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092168		gyg	Toys (CEOI18_toy)	C++17	100 / 100	1065 ms	4520 KiB

toy

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vct vector

int k;

vct<int> prds;
set<int> ans;
void bcktr(int nm = k, int prv_prd = 2) {
    if (nm != 1 && nm < prv_prd) return;
    if (nm == 1) { 
        int cnt = 0;
        for (int x : prds) cnt += x - 1;
        ans.insert(cnt);
        return; 
    }
    
    vct<int> dvs;
    for (int dv = 1; dv * dv <= nm; dv++) {
        if (nm % dv != 0) continue;
        if (dv != 1 && dv >= prv_prd) dvs.push_back(dv);
        if (nm / dv != dv && nm / dv >= prv_prd) dvs.push_back(nm / dv); 
    }
        
    for (int dv : dvs) {
        prds.push_back(dv);
        bcktr(nm / dv, dv);
        prds.pop_back();
    }
}

signed main() {
    // freopen("tys.in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    cin >> k;

    bcktr();

    cout << ans.size() << '\n';
    for (int x : ans) cout << x << " ";
    cout << '\n';
}

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