# Cod sursa(job #6010)

Utilizator Data 16 ianuarie 2007 19:21:16 Descompuneri 0 cpp done Arhiva de probleme 1.32 kb
``````#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define PB push_back

long long N;
int K, NF;
vector <long long> F;
vector <vector <int> > DP;

FILE *fin = fopen("desc.in", "rt");

fscanf(fin, " %lld %d", &N, &K);

fclose(fin);
}

void factori() {
int i, stop;

stop = (int) sqrt((double) N);

F.PB(1); F.PB(N);

for (i = 2; i < stop; ++i)
if (N % i == 0)
F.PB(i), F.PB(N / i);

if (N % stop == 0)
F.PB(stop);

sort(F.begin(), F.end());

NF = F.size();
}

void dinamica() {
int i, j, k, d;

DP.resize(NF);

for (i = 0; i < NF; ++i)
DP[i].resize(NF + 1);

for (j = 0; j < NF; ++j)
DP[0][j] = 1;

for (i = 1; i < NF; ++i)
for (j = i, k = 0; j; --j) {
DP[i][j] = DP[i][j + 1];

if (F[i] % F[j] == 0) {
d = F[i] / F[j];

while (F[k] < d) ++k;

DP[i][j] += DP[k][j];
}
}
}

void write() {
FILE *fout = fopen("desc.out", "wt");

fprintf(fout, "%d\n", DP[NF - 1][1]);

int i, j, d;

i = 1; j = NF - 1;
while (N > 1) {
while (N % F[i]) ++i;
d = N / F[i];
while (F[j] > d) --j;

if (DP[j][i] < K)
K -= DP[j][i++];
else {
fprintf(fout, "%lld ", F[i]);
N /= F[i];
}
}

fprintf(fout, "\n");

fclose(fout);
}

int main() {