Cod sursa(job #2532561)

Utilizator mahmoudbadawyMahmoud Badawy mahmoudbadawy Data 27 ianuarie 2020 22:57:31
Problema Descompuneri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

vector<long long> divi;
vector< pair<int,int> > v[5505];
long long n,k;
long long mem[5505][5505];

void calc(int x)
{
	int l=0,r=divi.size()-1;
	long long cur=divi[x];
	for(;l<divi.size();l++)
	{
		while(r>=0&&divi[l]*divi[r]>divi[x]) r--;
		if(r<0) break;
		if(divi[l]*divi[r]==divi[x])
			v[x].push_back({l,r});
	}
}

long long go(int las,int cur)
{
	if(cur==0) return 1;
	if(divi[las]>divi[cur]) return 0;
	if(mem[las][cur]!=-1) return mem[las][cur];
	mem[las][cur]=0;
	for(int i=1;i<v[cur].size();i++)
	{
		if(divi[v[cur][i].first]<divi[las]) continue;
		mem[las][cur]+=go(v[cur][i].first,v[cur][i].second);
	}
	return mem[las][cur];
}

vector<long long> ans;

void build(int las,int cur,long long k)
{
	if(cur==0) return;
	for(int i=1;i<v[cur].size();i++)
	{
		if(divi[v[cur][i].first]<divi[las]) continue;
		if(k>=go(v[cur][i].first,v[cur][i].second))
		{
			k-=go(v[cur][i].first,v[cur][i].second);
		}
		else
		{
			ans.push_back(divi[v[cur][i].first]);
			build(v[cur][i].first,v[cur][i].second,k);
			return;
		}
	}
}

int main()
{
	freopen("desc.in","r",stdin); freopen("desc.out","w",stdout);
	cin >> n >> k;
	for(long long i=1;i*i<=n;i++)
	{
		if(n%i) continue;
		divi.push_back(i);
		if(n/i!=i) divi.push_back(n/i); 
	}
	/*if(divi.size()>500) {
		cout << "NOOOOOOOOOOOOOO" << endl;
		return 0;
	}*/
	sort(divi.begin(),divi.end());
	for(int i=1;i<divi.size();i++)
	{
		calc(i);
	}
	memset(mem,-1,sizeof mem);
	cout << go(0,divi.size()-1) << endl;
	build(0,divi.size()-1,k-1);
	for(auto i:ans)
		cout << i << " ";
	cout << endl;
}