Cod sursa(job #385829)

Utilizator AndreyPAndrei Poenaru AndreyP Data 23 ianuarie 2010 15:46:43
Problema Descompuneri Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 5000
long long n;
long long k;
long long d[N];
long long a[N][N];
long long rez[N];
inline long long next(long long i,long long j)
{
	for(; d[i]%d[j]!=0; ++j)
		;
	return j;
}
int main()
{
	freopen("desc.in","r",stdin);
	freopen("desc.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	d[0]=1;
	d[1]=n;
	long long i;
      //  int lim=(int)sqrt((double)n);
	for(i=2; i*i<n; ++i)
	{
		if(n%i==0)
		{
			d[++d[0]]=i;
			d[++d[0]]=n/i;
		}
	}
	if(i*i==n)
		d[++d[0]]=i;
	sort(d+1,d+d[0]+1);

	long long t;
	long long x;
	for(i=1; i<=d[0]; ++i)
	{
		t=1;
		for(long long j=i; j!=0; --j)
		{
                	a[i][j]=a[i][j+1];
			if(d[i]%d[j]==0)
			{
				x=d[i]/d[j];
				if(x==1)
					++a[i][j];
				else
				{
					for(; d[t]!=x && t<d[0]; ++t)
						;
					a[i][j]+=a[t][j];
				}
			}
		}
	}
	printf("%lld\n",a[d[0]][1]);
       // return 0;


	long long j;
	i=d[0];
	j=1;
	t=1;
	long long cat;
        while(k!=0)
	{
		j=next(i,j);
		if(i==j)
		{
			rez[++rez[0]]=d[i];
			k=0;
			continue;
		}
                t=next(i,j+1);
		cat=a[i][j];
		while(k>cat-a[i][t])
		{
			k-=cat-a[i][t];
			cat=a[i][t];
			j=t;
			t=next(i,j+1);
		}
		rez[++rez[0]]=d[j];
		x=d[i]/d[j];
		for(; d[i]!=x; --i)
			;
	}
	for(i=1; i<rez[0]; ++i)
		printf("%lld ",rez[i]);
	printf("%lld\n",rez[rez[0]]);
	return 0;
}