Cod sursa(job #143797)

Utilizator allynaAlina S allyna Data 26 februarie 2008 21:13:55
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<stdio.h>
#include<math.h>

#define dmax 2870

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;


 }
long long caut(long long x)
{long long ls=1,ld=div[0],mij;

 while(ls<=ld)
  {mij=(ls+ld)/2;
   if(div[mij]<x)
	 ls=mij+1;
   else
	  if(div[mij]>x)
		 ld=mij-1;
	  else
		return mij;

	}
 }


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=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;

 }