Submission #1223936

#TimeUsernameProblemLanguageResultExecution timeMemory
1223936LeonidCukToys (CEOI18_toy)C++20
79 / 100
5096 ms56552 KiB
#include <bits/stdc++.h>
using namespace std;
vector<int>fact;
vector<set<int>>dp;
void vrni(int a,vector<pair<int,int>>&v,int l)
{
    fact.push_back(a);
    if(a==1)return;
    for(int i=l;i<v.size();i++)
    {
        if(v[i].second!=0)
        {
            v[i].second--;
            vrni(a/v[i].first,v,i);
            v[i].second++;
        }
    }
}
void vmerge(int k,int a,int b)
{
    for(auto it=dp[a].begin();it!=dp[a].end();it++)
    {
        for(auto it1=dp[b].begin();it1!=dp[b].end();it1++)
        {
            dp[k].insert(*it+*it1);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    map<int,int>m;
    int n,k;
    cin>>n;
    k=n;
    vector<pair<int,int>>v;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)v.push_back({i,0});
        while(n%i==0)
        {
            n=n/i;
            (v.back()).second++;
        }
    }
    if(n!=1)v.push_back({n,1});
    vrni(k,v,0);
    sort(fact.begin(),fact.end());
    for(int i=0;i<fact.size();i++)m[fact[i]]=i;
    dp.resize(fact.size());
    for(int i=0;i<fact.size();i++)
    {
        dp[i].insert(fact[i]-1);
        for(int j=i-1;j>=0;j--)
        {
            if(fact[i]%fact[j]==0)
            {
                vmerge(i,j,m[fact[i]/fact[j]]);
            }
        }
    }
    cout<<dp[dp.size()-1].size()<<endl;
    for(auto it=dp[dp.size()-1].begin();it!=dp[dp.size()-1].end();it++)
    {
        cout<<*it<<" ";
    }
}
#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...