Cod sursa(job #1267872)

Utilizator ELHoriaHoria Cretescu ELHoria Data 20 noiembrie 2014 13:36:38
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>

using namespace std;

int k;
int v[1024], sol[1024], z, l;

int count(int i,vector<long long>& d,long long val, const long long& tar) {
    if (val == tar) {
        k--;
        if (!k) {
            memcpy(sol, v, 4 * (z + 1));
            l = z;
        }
        return 1;
    }
    int ret = 0;
    if (tar % (val * d[i]) == 0) {
        v[z++] = d[i];
        ret += count(i, d, val * d[i], tar);
        z--;
    }

    if (i + 1 < (int)d.size() && tar / val > d[i]) {
        ret += count(i + 1, d, val, tar);
    }

    return ret;
}

int main() {
    ifstream cin("desc.in");
    ofstream cout("desc.out");
    long long n;
    cin >> n >> k;
    vector<long long> d;
    for (int i = 1; 1LL * i * i <= n; i++) {
        if (n % i == 0) {
            long long j = n / i;
            d.push_back(j);
            if (1LL * i * i != n) {
                d.push_back(n / j); 
            }
        }
    }

    sort(begin(d), end(d));
    cout << count(1, d, 1, n) << "\n";
    for (int i = 0; i < l; i++) {
        cout << sol[i] << " ";
    }
    return 0;
}