Cod sursa(job #478583)

Utilizator freak93Adrian Budau freak93 Data 19 august 2010 11:59:34
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="desc.in";
const char oname[]="desc.out";
const int maxn=3005;

ifstream f(iname);
ofstream g(oname);

int d[maxn],a[maxn][maxn],i,j,n,k,p,r;

int main()
{
    f>>n>>k;
    for(i=2;i*i<n;++i)
        if(n%i==0)
            d[++p]=i,d[++p]=n/i;
    if(i*i==n)
        d[++p]=i;
    d[++p]=n;
    sort(d+1,d+p+1);
    for(i=1;i<=p;++i)
        a[0][i]=1;
    d[0]=1;
    for(i=1;i<=p;++i)
    {
        r=0;
        for(j=p;j;--j)
        {
            a[i][j]=a[i][j+1];
            if(d[i]%d[j])
                continue;
            while(d[r]<d[i]/d[j])
                ++r;
            a[i][j]+=a[r][j];
        }
    }
    g<<a[p][1]<<"\n";
    j=1;
    for(i=p;i;)
    {
        r=p;
        for(;j<=p;++j)
            if(d[i]%d[j]==0)
            {
                while(d[r]>d[i]/d[j])
                    --r;
                if(a[r][j]<k)
                    k-=a[r][j];
                else
                {
                    g<<d[j]<<" ";
                    i=r;
                    break;
                }
            }
    }
}