Cod sursa(job #2559385)

Utilizator anamariatoaderAna-Maria Toader anamariatoader Data 27 februarie 2020 11:51:49
Problema Descompuneri Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <unordered_map>
#include <algorithm>

using namespace std;

ifstream fin ("desc.in");
ofstream fout ("desc.out");

int k,v[100005],d[1005][1005],nr,i,j;
long long n;
unordered_map <long long, int> h;

int main () {
    fin>>n>>k;
    for(i=1;1ll*i*i<n;i++){
        if(n%i==0){
          v[++nr]=i;
          v[++nr]=n/i;
        }
    }
    if(i*i==n)
        v[++nr]=i;
    sort(v+1,v+nr+1);
    for ( i = 1; i <= nr; i++ )
        h[v[i]] = i;
    for ( i = 1; i <= nr; i++ )
        d[1][i] = 1;
    for(i=2;i<=nr;i++){
        d[i][i]=1;
        for(j=i-1;j>1;j--){
            d[i][j]=d[i][j+1];
            if(v[i]%v[j]==0){
                long long dv = v[i] / v[j];
                int poz = h[dv];
                d[i][j]+=d[poz][j];
            }
        }
        d[i][1]=d[i][2];
    }
    fout<<d[nr][1]<<'\n';
    i=2;
    while(n!=1){
        for(;i<=nr;i++){
            if(n%v[i]==0){
                long long div=n/v[i];
                int pd=h[div];
                if(d[pd][i]<k)
                    k-=d[pd][i];
                else{
                    fout<<v[i]<<' ';
                    n=div;
                    break;
                }
            }
        }
    }
    return 0;
}