Cod sursa(job #50546)

Utilizator C_OvidiuCotletz Ovidiu C_Ovidiu Data 7 aprilie 2007 21:13:33
Problema Descompuneri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>
#include<math.h>

#define dmax 2500

long long div[dmax],N,K;
unsigned long sum[dmax][dmax],D[dmax][dmax];

void readdata()
{
 freopen("desc.in","r",stdin);
  scanf("%lld%lld",&N,&K);
 }

void desc()
{float rad;
 long long d,c=1;


 for(d=2,rad=sqrt(N);d<=rad;d++)
   if(!(N%d))
	  div[++div[0]]=d;
 if(N/div[div[0]]!=div[div[0]])
   {div[1+div[0]++]=N/div[div[0]];
	c=2;
	}

 for(d=div[0]-c;d>=1;d--)
   div[++div[0]]=N/div[d];
 div[++div[0]]=N;


 }

void  solve()
{long long i,j,n,k,l;
 //memset(sum,0,sizeof(sum));

 for(i=1,n=div[0];i<=n;i++)
   {
	D[i][i]=1;
	for(j=1;j<i;j++)
	 if(div[i]%div[j]==0)
	   {l=div[i]/div[j];
		l=1;
		//caut l
		/*for(k=1;k<=i;k++)
		  if(l==div[k])
		   {l=k;break;}
		  */
		D[i][j]+=sum[l][j];

		}
	sum[i][div[0]+1]=0;
	for(j=div[0];j>=1;j--)
	 sum[i][j]=sum[i][j+1]+D[i][j];

	}









 }
void afis(unsigned long p,unsigned long min)
{long long i,l,j;
 if(!K) return;
 for(i=min;i<=div[0];i++)
  if(D[p][i]>=K)
	{
	 printf("%lld ",div[i]);
	 l=div[p]/div[i];
	 for(j=1;j<=div[0];j++)
	  if(l==div[j])
		{l=j;break;}
	 if(j==div[0]+1)
	   l=0;

	 afis(l,i);
	 return;
	 }
  else
	K-=D[p][i];

 }




void printdata()
{long long s=0,i;
freopen("desc.out","w",stdout);
for(i=1;i<=div[0];i++)
  s+=D[div[0]][i];

printf("%lld\n",s);
afis(div[0],1);
 fclose(stdout);



 }









int main()
{

 readdata();
 desc();
 solve();
 printdata();

 return 0;

 }