Cod sursa(job #3233328)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 23:29:38
Problema Descompuneri Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to find all increasing sequences whose product is N
void findSequences(long long N, long long start, vector<long long>& sequence, vector<vector<long long>>& allSequences) {
    if (N == 1) {
        if (!sequence.empty()) {
            allSequences.push_back(sequence);
        }
        return;
    }
    for (long long i = start; i * i <= N; ++i) {
        if (N % i == 0) {
            sequence.push_back(i);
            findSequences(N / i, i, sequence, allSequences);
            sequence.pop_back();
        }
    }
    if (N >= start) {
        sequence.push_back(N);
        allSequences.push_back(sequence);
        sequence.pop_back();
    }
}

int main() {
    ifstream infile("desc.in");
    ofstream outfile("desc.out");

    long long N;
    int K;
    infile >> N >> K;

    vector<vector<long long>> allSequences;
    vector<long long> sequence;

    findSequences(N, 2, sequence, allSequences);

    sort(allSequences.begin(), allSequences.end());

    outfile << allSequences.size() << endl;
    if (K <= allSequences.size()) {
        for (long long num : allSequences[K - 1]) {
            outfile << num << " ";
        }
        outfile << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}