Cod sursa(job #14537)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 9 februarie 2007 11:55:39
Problema Descompuneri Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int NMAX = 4096;

long long N;
int K, NF;
long long F[NMAX];
int DP[NMAX][NMAX];

void read() {
	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[0] = 1; F[1] = N; NF = 2;

	for (i = 2; i < stop; ++i)
		if (N % i == 0) {
			F[NF++] = i;
			F[NF++] = N / i;
		}
	
	if (stop > 1 && N % stop == 0) F[NF++] = stop;

	sort(F, F + NF);
}

void dinamica() {
	int i, j, k;
	long long stop;

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

	for (i = 1; i < NF; ++i) {
		
		k = 0;

		for (j = NF - 1; j; --j) {
			
			DP[i][j] = DP[i][j + 1];

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

				for (stop = F[i] / F[j]; F[k] < stop; ++k);

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

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

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

	fclose(fout);
}

int main() {
	
	read();

	factori();

	dinamica();

	write();

	return 0;
}