Cod sursa(job #14012)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 8 februarie 2007 00:42:35
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#include <algorithm>
#define nmax 3000
#define pt(i) (1<<(i))

using namespace std;

typedef long long lint;

lint n,dvz[nmax];
int k,N,nr[nmax][nmax];
char a[nmax][nmax];

bool cmp(const lint i,const lint j)
{
  return(i<j);
}

lint find(lint x)
{
  int i,j;
  for(j=0,i=15;i>=0;i--)
    if(j+pt(i)<=N&&dvz[j+pt(i)]<=x)
      j+=pt(i);
  return(dvz[j]==x?j:0);  
}

int main()
{
  FILE *fi=fopen("desc.in","r"),*fo=fopen("desc.out","w");  
  fscanf(fi,"%lld %d",&n,&k);
  lint i,j,z,g,x;
  for(N=0,i=1;i*i<=n;i++)
    if(!(n%i))
    {
      dvz[++N]=i;
      if(n!=i*i)
        dvz[++N]=n/i;
    }
  sort(dvz+1,dvz+N+1,cmp);
  printf("%d\n",N);
  nr[N+1][1]=1;
  for(i=N;i>1;i--)
  {
    memcpy(nr[i],nr[i+1],sizeof(nr[i+1]));
    for(z=find(n/dvz[i]),j=1;j<=z;j++)
      if(!(n%(g=dvz[i]*dvz[j])))
    {      
      nr[i][find(g)]+=nr[i][j];
      nr[i][0]=0;
    }
  }
  fprintf(fo,"%d\n",nr[2][N]);
  for(i,j=2,x=n;x!=1;)
  {
    for(i=j;i<=N;i++)
    {
      if(x%dvz[i])
	continue;
      if(nr[i][z=find(x/dvz[i])]<k)
	k-=nr[i][z];
      else
      {
	fprintf(fo,"%d ",dvz[i]);
	j=i;x/=dvz[i];
	break;
      }
    }
  }
  fprintf(fo,"\n");
  printf("%d\n",nr[2][N]);
  return(0);
}