Cod sursa(job #20208)

Utilizator diaDiana Adrisor dia Data 20 februarie 2007 20:45:07
Problema Descompuneri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define NMAX 1020

using namespace std;

int A[NMAX][NMAX], N, K, M, Sol[NMAX];
vector<int> D;

int cb(int x)
{
        int lo, hi, mid;

        for (lo = 0, hi = M-1, mid = (lo+hi)/2; lo <= hi; mid = (lo+hi)/2)
        {
                if (x == D[mid]) return mid;
                if (x < D[mid]) hi = mid-1;
                else lo = mid+1;
        }
        return -1;
}

int main()
{
        int i, j, rad, p, nsol = 0;

        freopen("desc.in", "r", stdin);
        scanf("%d %d", &N, &K);

        rad = (int)sqrt(N);
        D.push_back(1);
        for (i = 2; i <= rad; i++)
            if (N%i == 0) D.push_back(i), D.push_back(N/i);

        D.push_back(N);
        sort(D.begin(), D.end());
        M = D.size();

        for (i = 0; i < M; i++) A[0][i] = 1;

        for (i = 1; i < M; i++)
            if (D[i] != D[i-1])
            {
            for (j = i; j > 0; j--)
            {
                A[i][j] = A[i][j+1];
                p = -1;
                if (D[i]%D[j] == 0)
                   p = cb(D[i]/D[j]);
                if (p >= 0) A[i][j] += A[p][j];
            }
            }
            else
            for (j = 0; j < M; j++) A[i][j] = A[i-1][j];
                
        freopen("desc.out", "w", stdout);
        printf("%d\n", A[M-1][1]);

        for (i = n-1; i > 0; i--)
            for (j = 0; j < N; j++)
                if (A[i][j] > K && A[i][j-1] < K) { K -= A[i][j]; break; }
        p = i;

        while (p > 1)
        {
                Sol[nsol++] = p;
                p = N/p;
        }

        for (i = nsol-1; i >= 0; i--) printf("%d ", Sol[i]);
        printf("\n");

        return 0;
        
}