# Cod sursa(job #14009)

Utilizator Data 8 februarie 2007 00:39:49 Descompuneri 100 c done Arhiva de probleme 1.49 kb
``````#include <stdio.h>
#include <stdlib.h>

#define MAX_D 3000
#define FIN "desc.in"
#define FOUT "desc.out"

long long N, D[MAX_D];
int K, nd, S[MAX_D][MAX_D], Res;

int cmp(const void *i, const void *j)
{
if (*(long long *) i < *(long long *) j)
return -1;
return +1;
}

int find(long long x)
{
int i, step;

for (step = 1; step < nd; step <<= 1);
for (i = 0; step; step >>= 1)
if (i+step < nd && D[i+step] <= x)
i += step;
return i;
}

void solve(int i, int k, long long n, int p)
{
int j, s;

if (!i) return;
for (j = k, s = 0; j <= i; j++)
if (S[i][j]-S[i][k-1] >= p) break;
printf("%lld ", D[j]);
solve(find(D[i] / D[j]), j, n / D[j], p-S[i][j-1]+S[i][k-1]);
}

int main(void)
{
long long i; int j, k;

freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);

scanf("%lld %d", &N, &K);

for (i = 1; i * i <= N; i++)
if (N % i == 0)
{
D[nd++] = i;
if (i < N/i) D[nd++] = N/i;
}

qsort(D, nd, sizeof(long long), cmp);

for (i = 1; i < nd; i++)
{
for (j = 1; j < i; j++)
{
S[i][j] = S[i][j-1];
if (D[i] % D[j]) continue;
k = find(D[i] / D[j]);
S[i][j] += j <= k ? S[k][k]-S[k][j-1] : 0;
}
S[i][i] = S[i][i-1]+1;
}

printf("%d\n", S[nd-1][nd-1]);
solve(nd-1, 1, N, K);
putchar('\n');

return 0;
}``````