Cod sursa(job #14008)

Utilizator dominoMircea Pasoi domino Data 8 februarie 2007 00:39:49
Problema Descompuneri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 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;
}