# Cod sursa(job #2559265)

Utilizator Data 27 februarie 2020 10:32:27 Descompuneri 100 cpp-64 done Arhiva de probleme 1.49 kb
``````#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

#define N 4095

using namespace std;

ifstream f ( "desc.in" );
ofstream g ( "desc.out" );

unordered_map < long long, int > h;
int d[N][N];
long long n, k, v[N], dv;

int main()
{   int l = 0, i, j;
f >> n >> k;
for ( dv = 1; dv * dv < n; dv++ ){
if ( n % dv == 0 ){
v[++l] = dv;
v[++l] = n / dv;
}
}
if ( dv * dv == n )
v[++l] = dv;
sort ( v + 1, v + l + 1 );
for ( i = 1; i <= l; i++ )
h[v[i]] = i;
for ( i = 1; i <= l; i++ )
d[1][i] = 1;
for ( i = 2; i <= l; i++ ){
d[i][i] = 1;
for ( j = i - 1; j >= 2; j-- ){
d[i][j] = d[i][j + 1];
if ( v[i] % v[j] == 0 ){
dv = v[i] / v[j];
int poz = h[dv];
d[i][j] += d[poz][j];
}
}
d[i][1] = d[i][2];
}
g << d[l][1] << '\n';
int line = l;
long long num = n;
int start = 2;
while ( num > 1 ){
for ( i = start; i <= line; i++ ){
if ( num % v[i] == 0 ){
dv = num / v[i];
if ( d[h[dv]][i] >= k ){
start = i;
break;
}
else
k -= d[h[dv]][i];
}
}
g << v[i] << ' ';
num = num / v[i];
line = h[num];
}
return 0;
}
``````