Submission #1039272

#TimeUsernameProblemLanguageResultExecution timeMemory
1039272slivajanToys (CEOI18_toy)C++17
79 / 100
5062 ms70912 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long un;
typedef vector<un> vuc;
typedef set<un> sun;

#define vec vector
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define ALL(x) (x).begin(), (x).end()


unordered_map<un, sun> cache;
vuc divi;

void answer(un a){
    if (cache.count(a) != 0) return;

    sun ret;
    ret.insert(a-1);

    for(un i = 0; divi[i]*divi[i] <= a; i++){
        if (a%divi[i] != 0) continue;
        
        un d = divi[i];

        if (cache.count(d) == 0) answer(d);
        if (cache.count(a/d) == 0) answer(a/d);

        FEAC(sa, cache[d]) FEAC(sb, cache[a/d]){
            ret.insert(sa + sb);
        }
    }

    cache[a] = ret;
}

void prep_div(un a){

    un sqrt_a = 1;
    while (sqrt_a * sqrt_a <= a) sqrt_a++;

    sqrt_a++;

    REP(i, 2, sqrt_a){
        if (a % i == 0) divi.push_back(i);
    }

    divi.push_back(a+1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    un N;
    cin >> N;

    prep_div(N);
    answer(N);
    sun ans = cache[N];

    cout << ans.size() << endl;
    FEAC(i, ans) cout << i << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...