Cod sursa(job #1756995)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 14 septembrie 2016 09:45:53
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXDIV 3010

using namespace std;

long long n, k;
long long sir[MAXDIV];
int din[MAXDIV][MAXDIV], nq;
vector<int> sol;

void divizori()
{
    long long d;
    for (d = 1; d*d < n; d++)
        if (n % d == 0) {
            sir[++nq] = d;
            sir[++nq] = n/d;
        }
    if (d * d == n)
        sir[++nq] = d;
    sort(sir+1, sir+nq+1);
}

void dp()
{
    for (int i = 1; i <= nq; i++)
        din[1][i] = 1;
    for (int i = 2; i <= nq; i++) {
        int iind = 1;
        for (int j = i; j >= 2; j--) {
            din[i][j] = din[i][j+1];
            if (sir[i] % sir[j] == 0) {
                long long ndiv = sir[i] / sir[j];
                while (sir[iind] < ndiv) iind++;
                din[i][j] += din[iind][j];
            }
        }
    }
}

void buildKth()
{
    int iind = nq, i = nq, j = 2;
    long long exp = k;
    while (din[i][j] != 1) {
        if (sir[i] % sir[j] == 0) {
            long long ndiv = sir[i] / sir[j];
            while (sir[iind] > ndiv) iind--;
        }
        if (sir[i] % sir[j] != 0 || exp > din[iind][j]) {
            if (sir[i] % sir[j] == 0)
                exp -= din[iind][j];
            j++;
        }
        else
        {
            sol.push_back(sir[j]);
            i = iind;
        }
    }
    sol.push_back(sir[i]);
}

int main()
{
    freopen("desc.in", "r", stdin);
    freopen("desc.out", "w", stdout);

    scanf("%lld %lld", &n, &k);
    divizori();
    dp();
    printf("%d\n", din[nq][2]);
    buildKth();
    for (int nr : sol)
        printf("%d ", nr);

    return 0;
}