Submission #96392

#TimeUsernameProblemLanguageResultExecution timeMemory
96392easruiToys (CEOI18_toy)C++14
100 / 100
823 ms7092 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5;
int N,tmp,fac[MAX],num[MAX],selA[MAX],selB[MAX],posA,posB,cnt,res,ans,A,B,C;
vector<int> pows[MAX];
set<int> S;
bool isP[MAX];

void act(int cur, int val, int sum)
{
    if(val>=cur) S.insert(sum+cur-1);
    if(cur==1) return;
    for(int i=2; i<=min(val,cur/i); i++){
        if(cur%i) continue;
        if(i<=val) act(cur/i,i,sum+i-1);
        if(cur/i<=val) act(i,cur/i,sum+cur/i-1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N;
    act(N,N,0);
    cout << S.size() << '\n';
    for(auto it : S) cout << it << ' ';
    /*tmp = N;
    for(int i=0; i<MAX; i++) isP[i] = true;
    for(int i=2; i*i<=N; i++){
        if(isP[i]){
            for(int j=2; j*j*i*i<=N; j++) isP[j*i] = false;
            if(tmp%i==0) fac[++cnt] = i;
            while(tmp%i==0){
                num[cnt]++;
                tmp /= i;
            }
        }
    }
    if(tmp!=1){
        fac[++cnt] = tmp;
        num[cnt]++;
    }
    for(int i=1; i<=cnt; i++){
        pows[i].push_back(1);
        for(int j=1; j<=num[i]; j++){
            pows[i].push_back(pows[i][j-1]*fac[i]);
        }
    }
    A = B = 1;
    S.insert(A+B+(N/A/B));
    while(1){
        for(posB= 1; posB <= cnt; posB++){
            if(selB[posB]<num[posB]-selA[posB]){
                selB[posB]++;
                B *= fac[posB];
                break;
            }
            B /= pows[posB][num[posB]-selA[posB]];
            selB[posB] = 0;
        }
        if(posB>cnt) break;
        S.insert(A+B+(N/A/B));
    }
    while(1){
        for(posA = 1; posA <= cnt; posA++){
            if(selA[posA]<num[posA]){
                selA[posA]++;
                A *= fac[posA];
                break;
            }
            A /= pows[posA][num[posA]];
            selA[posA] = 0;
        }
        if(posA>cnt) break;
        B = 1;
        S.insert(A+B+(N/A/B));
        for(int pos = 1; pos <= cnt ; pos++) selB[pos] = 0;
        while(1){
            for(posB= 1; posB <= cnt; posB++){
                if(selB[posB]<num[posB]-selA[posB]){
                    selB[posB]++;
                    B *= fac[posB];
                    break;
                }
                B /= pows[posB][num[posB]-selA[posB]];
                selB[posB] = 0;
            }
            if(posB>cnt) break;
            S.insert(A+B+(N/A/B));
        }
    }
    cout << S.size() << '\n';
    for(auto it : S) cout << (it-3) << ' ';*/
}
#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...