Cod sursa(job #1039469)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 23 noiembrie 2013 09:08:04
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <algorithm>
using namespace std;
long long N, K, sol, nsol;
long long f[100], dvz[1000100], afis[100], desc[100];
int nrf, e[100], nrdvz;

inline void BackDiv(int pas, long long val)
{
	if(pas == nrf + 1)
	{
		if(val > 1LL)
			dvz[++nrdvz] = val;
	}
	else
	{
		int i;
		long long newval = val;
		BackDiv(pas + 1, val);
		for(i = 1; i <= e[pas]; ++i)
		{
			newval *= f[pas];
			BackDiv(pas + 1, newval);
		}
	}
}

inline void Back(int pas, long long prod, int ind)
{
	if(prod == N)
	{
		sol++;
		if(sol == K)
		{
			for(int i = 1; i < pas; ++i)
				afis[i] = desc[i];
			nsol = pas - 1;
		}
	}
	else
	{
		if(ind > nrdvz)
			return;
		if(prod * dvz[ind] <= N)
		{
			desc[pas] = dvz[ind];
			Back(pas + 1, prod * dvz[ind], ind);
			Back(pas, prod, ind + 1);
		}
		
	}
}

int main()
{
	ifstream fin("desc.in");
	fin >> N >> K;
	fin.close();
	
	long long aux = N;
	if(aux % 2LL == 0LL)
	{
		f[++nrf] = 2LL;
		while(aux % 2LL == 0LL)
		{
			e[nrf]++;
			aux /= 2LL;
		}
	}
	for(int i = 3; 1LL * i * i <= aux; i += 2)
	{
		if(aux % (1LL * i) == 0LL)
		{
			f[++nrf] = i;
			while(aux % (1LL * i) == 0LL)
			{
				e[nrf]++;
				aux /= (1LL * i);
			}
		}
	}
	if(aux > 1LL)
	{
		f[++nrf] = aux;
		e[nrf] = 1;
	}
	
	BackDiv(1, 1LL);
	sort(dvz + 1, dvz + nrdvz + 1);
	Back(1, 1LL, 1);
	
	ofstream fout("desc.out");
	fout << sol << "\n";
	for(int i = 1; i <= nsol; ++i)
		fout << afis[i] << ' ';
	fout << "\n";
	fout.close();
	return 0;
}