Cod sursa(job #839282)

Utilizator cat_red20Vasile Ioana cat_red20 Data 21 decembrie 2012 17:00:09
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[3001][3001],k,d;
long long dvz[3001],n;

void citire()
{
    freopen("desc.in","r",stdin);
    scanf("%lld %d",&n,&k);
}

void divizori()
{
    for(long long i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            dvz[d++]=i;
            if(i!=n/i)
            {
                dvz[d++]=n/i;
            }
        }
    }
    sort(dvz,dvz+d);
    d--;
  /*  for(int i=0;i<d;i++)
    {
        dvz[2*d-i-1]=n/dvz[i];
    }
    d=d*2;
    d--;*/
}

void din()
{
    int x;
    for(int i=1;i<=d;i++)
    {
        x=0;
        a[i][i]=1;
        a[0][i]=1;
        for(int j=i-1;j>=1;j--)
        {
            a[i][j]=a[i][j+1];
            if(dvz[i]%dvz[j]==0)
            {
                for(;dvz[x]<dvz[i]/dvz[j];x++);
                a[i][j]+=a[x][j];
            }
         //   printf("%d ",a[i][j]);
        }
        //printf("\n");
    }
}
int cauta(long long x,int p,int u)
{
    int m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(dvz[m]==x)
        return m;
        if(dvz[m]<x)
        p=m+1;
        else
        u=m-1;
    }
    return -1;
}

void afisare()
{
    int i,j,dvzp=1,u=d;
    freopen("desc.out","w",stdout);
    printf("%d\n",a[d][1]);
  while(k!=0 && j!=0)
    {

        for(i=dvzp;i<=u;i++)
        {
            if(dvz[u]%dvz[i]!=0)
            continue;
            j=cauta(dvz[u]/dvz[i],0,u);
            if(a[j][i]<k && j!=-1)
            {
                k-=a[j][i];
            }
            else
            if(j!=-1)
            {
                printf("%lld ",dvz[i]);
                dvzp=i;
                u=j;
                break;
            }
        }
    }
}

int main()
{
    citire();
    divizori();
    din();
    afisare();
    return 0;
}