Submission #1039132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039132		0npata	Toys (CEOI18_toy)	C++17	59 / 100	5059 ms	780 KiB

toy

#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int long long


set<int> ans;
vec<pair<int, int>> primes(0);

int n;

 
void find_primes() {
    int cn = n;
    for(int i = 2; i*i <= cn; i++) {
       if(cn % i == 0) {
           primes.push_back({i, 0});
           while(cn % i == 0) {
               cn /= i;
               primes.back().second++;
           }
       }
    }
    if(cn != 1) primes.push_back({cn, 1});
}


void go(int cur, int lst, int id) {
    bool done = true;
    for(auto& [p, cnt] : primes) {
        int val = 1;
        for(int i = 0; i<cnt; i++) {
            val *= p;
            cnt -= (i+1); 
            if(cur * val >= lst) {
                go(1, cur*val, id + cur*val-1);
            }
            go(cur*val, lst, id);
            cnt += (i+1);
            done = false;
       }
    }
    if(done && cur == 1) {
        ans.insert(id); 
    }
}

int32_t main() {
    cin >> n;
    
    find_primes();
     
     go(1, 0, 0);

cout << ans.size() << '\n';
    for(int res : ans) {
        cout << res << ' ';
    }
    cout << '\n';
}

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