Submission #1168328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168328		altern23	Toys (CEOI18_toy)	C++20	100 / 100	4198 ms	79848 KiB

toy

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

vector<ll> ans;
unordered_map<ll, unordered_map<ll, ll>> mp;

vector<ll> D;

void calc(ll idx, ll sum){
    if(mp[idx].find(sum) != mp[idx].end()) return;
    mp[idx][sum] = 1;
    if(idx == 1){
        ans.push_back(sum);
        return;
    }
    for(auto i : D){
        if(i > idx) break;
        if(idx % i == 0){
            calc(idx / i, sum + i - 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n; cin >> n;
        for(ll i = 1; i * i <= n; i++){
            if(n % i) continue;
            if(i != 1) D.push_back(i);
            if(i != n / i) D.push_back(n / i);
        }
        
        sort(D.begin(), D.end());
        calc(n, 0);

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        cout << (int)ans.size() << "\n";
        for(auto i : ans) cout << i << " ";
        cout << "\n";
    }   
}

/*

*/ 

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