Cod sursa(job #356626)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 15 octombrie 2009 17:34:29
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#define lm 500

long long n, d[lm];
int m, l,  v[lm][lm];

void afisare (int p, int k)
{
	int i, j;
	long long c;
	if (p) 
	{
		for (i=k; v[p][i]-v[p][i+1]<m && i<=l; m-=v[p][i]-v[p][i+1], i++);
		c=d[p]/d[i];
		for (j=0; j<=l; j++) 
			if (d[j]==c) break;
		printf("%I64d ",d[i]);
		afisare(j,i);
	}
}
		

int main()
{
	freopen("desc.in","r",stdin);
	freopen("desc.out","w",stdout);
	scanf("%I64d %d",&n,&m);
	int i, j;
	long long h;
	for (h=2; h*h<=n; h++)
		if (!(n%h)) 
		{
			l++;
			d[l]=h;
		}
	if (d[l]*d[l]==n)
	{
		for (i=l+1; i<=2*l-1; i++) d[i]=n/d[l-(i-l)];
		l=2*l-1;
	} else
	{
		for (i=l+1; i<=2*l; i++) d[i]=n/d[l-i+l+1];
		l=2*l;
	}
	l++;
	d[l]=n;
	int p;
	for (i=1; i<=l; i++)
	{
		v[i][i]=1;
		p=1;
		for (j=i-1; j>0; j--) 
		{
			v[i][j]=v[i][j+1];
			if (!(d[i]%d[j]) && d[i]/d[j]>=d[j]) 
			{
				if (p<j) p=j;
				for (; d[p]!=d[i]/d[j] && p<=l; p++);
				v[i][j]+=v[p][j];
			}
		}
	}
	printf("%d\n",v[l][1]);
	d[0]=1;
	afisare(l,1);	
}