Cod sursa(job #689513)

Utilizator cnt_tstcont teste cnt_tst Data 24 februarie 2012 16:52:04
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
# include <algorithm>
# include <cstdio>
# include <vector>
using namespace std ;

typedef long long ll ;
const char *FIN = "desc.in", *FOU = "desc.out" ;
const int MAX = 3005 ;

vector < ll > D ;
int K, dp[MAX][MAX] ;
ll N ;

int main (void) {
    fscanf (fopen (FIN, "r"), "%lld %d", &N, &K) ;
    for (ll i = 2; i * i <= N; ++i) {
        if (N % i) continue ;
        D.push_back (i) ;
        if (i * i != N) {
            D.push_back (N / i) ;
        }
    }
    D.push_back (1), D.push_back (N), sort (D.begin (), D.end ()) ;
    N = D.size () - 1 ;
    for (int i = 1; i <= N; ++i)
        dp[0][i] = 1 ;
    for (int i = 1; i <= N; ++i) {
        for (int j = N, k = 0; j > 0 ; --j) {
            dp[i][j] = dp[i][j + 1];
            if (D[i] % D[j]) continue ;
            for ( ; D[k] < D[i] / D[j] && k <= N; ++k) ;
            dp[i][j] += dp[k][j] ;
        }
    }
    freopen (FOU, "w", stdout) ;
    printf ("%d\n", dp[N][1]) ;
    for (int i = N, j = 1; i ; ) {
        for (int k = N; j <= N; ++j) {
            if (D[i] % D[j]) continue ;
            for ( ; D[k] > D[i] / D[j] && k > 0 ; --k) ;
            if (dp[k][j] < K) K -= dp[k][j] ;
            else {
                printf ("%lld ", D[j]), i = k ;
                break ;
            }
        }
    }
}