Cod sursa(job #2711920)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 24 februarie 2021 21:28:37
Problema Descompuneri Scor 42
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

ifstream fin("desc.in");
ofstream fout("desc.out");

const int DMAX = 4096;
int K, dp[DMAX][DMAX], N;
int64 X, divs[DMAX];
unordered_map<int64,int> Hash;

int main() {
    fin >> X >> K;
    for(int64 d = 1; d * d <= X; ++d)
        if(X % d == 0) {
            divs[++N] = d;
            if(d != X / d)
                divs[++N] = X / d;
        }
    sort(divs + 1, divs + N + 1);
    for(int i = 1; i <= N; ++i) {
        Hash[divs[i]] = i;
        dp[1][i] = 1;
    }
    for(int i = 2; i <= N; ++i) {
        for(int j = i; j > 1; --j) {
            dp[i][j] = dp[i][j + 1];
            if(divs[i] % divs[j] == 0)
                dp[i][j] += dp[Hash[divs[i] / divs[j]]][j];
        }
        dp[i][1] = dp[i][2];
    }
    fout << dp[N][1] << '\n';
    int p = 2;
    while(X > 1)
        while(p <= N) {
            if(X % divs[p]) {
                ++p;
                continue;
            }
            int complement = X / divs[p];
            if(dp[Hash[complement]][p] < K)
                K -= dp[Hash[complement]][p++];
            else {
                fout << divs[p] << ' ';
                X = complement;
                break;
            }
        }
}