Cod sursa(job #5015)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 9 ianuarie 2007 17:12:08
Problema Descompuneri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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 <long long> > DP;

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

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

	fclose(fin);
}

void factori() {
	int i, stop;

	stop = (int) sqrt(N);

	for (i = 1; 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, "%lld\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() {
	
	read();

	factori();

	dinamica();

	write();

	return 0;
}