Cod sursa(job #2200385)

Utilizator lucametehauDart Monkey lucametehau Data 1 mai 2018 10:52:30
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <map>

using namespace std;

ifstream cin ("desc.in");
ofstream cout ("desc.out");

const int dmax = 3000;

long long n;
int k;
int diviz;

long long divi[1 + dmax];
int dp[1 + dmax][1 + dmax];
map <long long, int> ind;

void findPerm(int i, int j, int k) {
  if(i == 1)
    return;
  while(dp[i][j] - dp[i][j + 1] < k) {
    k -= dp[i][j] - dp[i][j + 1];
    j++;
  }
  cout << divi[j] << " ";
  findPerm(ind[divi[i] / divi[j]], j, k);
}

int main() {
  cin >> n >> k;
  for(int i = 1; 1LL * i * i <= n; i++)
    if(n % i == 0)
      divi[++diviz] = i;
  if(divi[diviz] * divi[diviz] == n)
    diviz = diviz * 2 - 1;
  else
    diviz *= 2;
  for(int i = diviz / 2 + 1 + diviz % 2; i <= diviz; i++)
    divi[i] = n / divi[diviz - i + 1];
  for(int i = 1; i <= diviz; i++)
    ind[divi[i]] = i;
  for(int i = 1; i <= diviz; i++)
    dp[i][i] = 1;
  for(int j = diviz - 1; j >= 1; j--) {
    for(int i = j + 1; i <= diviz; i++) {
      dp[i][j] = dp[i][j + 1];
      if(divi[i] % divi[j] == 0)
        dp[i][j] += dp[ind[divi[i] / divi[j]]][j];
    }
  }
  cout << dp[diviz][2] << "\n";
  findPerm(diviz, 2, k);
  return 0;
}