Cod sursa(job #2647043)

Utilizator shivensinha4Shiven Sinha shivensinha4 Data 2 septembrie 2020 19:31:45
Problema Descompuneri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'


int main() {
	#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	ll n, k; cin >> n >> k;
	vector<ll> div;
	for (int i = 1; i*i <= n; i++) if (n % i == 0) {
		if (i != 1) div.push_back(i);
		ll j = n/i;
		if (j != i) div.push_back(j);
	}
	
	sort(div.begin(), div.end());
	int dc = div.size();
	unordered_map<ll, int> id;
	for_(i, 0, dc) id[div[i]] = i;
	
	ll dp[dc+1][dc+1];
	memset(dp, 0, sizeof(dp));

	for_(i, 0, dc) {
		dp[i][i] = 1;
		for (int j = i-1; j >= 0; j--) {
			if ((div[i] % div[j]) == 0) dp[i][j] += dp[id[div[i] / div[j]]][j];
			dp[i][j] += dp[i][j+1];
		}
	}
	
	cout << dp[dc-1][0] << endl;
	
	for_(i, 0, dc) for_(j, 0, dc) {
		if (j != dc-1) dp[i][j] -= dp[i][j+1];
		if (j != 0) dp[i][j] += dp[i][j-1];
	}
	
	ll first = dc-1, prev = 0;
	while (true) {
		ll rem = (prev > 0 ? dp[first][prev-1] : 0);
		if (rem == dp[first][dc-1]) break;
		for_(i, prev, dc) if (i == dc-1 or dp[first][i]-rem >= k) {
			cout << div[i] << " ";
			k -= (i > 0 ? dp[first][i-1]-rem : 0);
			first = id[div[first]/div[i]];
			prev = i;
			break;
		}
	}
	
	cout << endl;
	

	return 0;
}