Cod sursa(job #1250228)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 octombrie 2014 22:02:13
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <algorithm>
#define DIM 3005
#define infile "desc.in"
#define outfile "desc.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int Divisors[DIM], D[DIM][DIM];

int n, k;

int main() {
	f >> n >> k;
	int nr_divisors = 0, i;
	Divisors[0] = 1;
	for (i = 2; i * i < n; ++i)
		if (n % i == 0)
			Divisors[++nr_divisors] = i, Divisors[++nr_divisors] = n / i;
	if (i * i == n)
		Divisors[++nr_divisors] = i;
	Divisors[++nr_divisors] = n;
	std::sort(Divisors, Divisors + nr_divisors + 1);
	for (i = 1; i <= nr_divisors; ++i)
		D[0][i] = 1;
	for (i = 1; i <= nr_divisors; ++i) {
		int pos = 0;
		for (int j = nr_divisors; j >= 1; --j) {
			D[i][j] = D[i][j + 1];
			if (Divisors[i] % Divisors[j] == 0) {
				for (; Divisors[pos] < Divisors[i] / Divisors[j]; ++pos);
				D[i][j] += D[pos][j];
			}
		}
	}
	g << D[nr_divisors][1] << "\n";
	int j = 1;
	for (i = nr_divisors; i >= 1;) {
		int pos = nr_divisors;
		for (; j <= nr_divisors; ++j) {
			if (Divisors[i] % Divisors[j] == 0) {
				for (; Divisors[pos] > Divisors[i] / Divisors[j]; --pos);
				if (D[pos][j] < k)
					k -= D[pos][j];
				else {
					g << Divisors[j] << " ";
					i = pos;
					break;
				}
			}
		}
	}
	return 0;
}

//Trust me, I'm the Doctor!