Cod sursa(job #1694835)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 aprilie 2016 00:21:18
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

const int DIM = 1 << 12;
using namespace std;

int Dp[DIM][DIM], M, K;
long long Div[DIM], N, minim;

int find_pos( long long val ) {
    int st = 1, dr = M, mid;

    while( st <= dr ) {
        mid = st + ( dr - st ) / 2;

        if( Div[mid] == val )
            return mid;

        if( Div[mid] < val )
            st = mid + 1;
        else
            dr = mid - 1;
    }

    return -1;
}

int main() {

    FILE *input_file  = fopen( "desc.in" , "r" );
    FILE *output_file = fopen( "desc.out", "w" );

    fscanf( input_file, "%lld %d", &N, &K );

    for( int i = 1; i * i <= N; i ++ ) {
        if( N % i != 0 )
            continue;

        Div[++M] = i;

        if( i * i != N )
            Div[++M] = N / i;
    }

    sort( Div + 1, Div + M + 1 );

    for( int i = 2; i <= M; i ++ ) {
        Dp[i][i] = 1;

        for( int j = i - 1; j >= 2; j -- ) {
            Dp[i][j] += Dp[i][j + 1];

            if( Div[i] % Div[j] == 0 && Div[i] / Div[j] >= Div[j] )
                Dp[i][j] += Dp[ find_pos( Div[i] / Div[j] ) ][j];
        }
    }

    fprintf( output_file, "%d\n", Dp[M][2] );

    for( int pos = M, minim = 2; pos >= 2; ) {
        if( K > Dp[pos][minim] - Dp[pos][minim + 1] ) {
            K -= Dp[pos][minim] - Dp[pos][minim + 1];
            minim ++;
        } else {
            fprintf( output_file, "%lld ", Div[minim] );
            pos = find_pos( Div[pos] / Div[minim] );
        }
    }

    return 0;
}