Cod sursa(job #1491218)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 24 septembrie 2015 22:44:30
Problema Descompuneri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
using namespace std;
ifstream f("desc.in");
ofstream g("desc.out");
long long N,K;
long long Div[2000005];
long long A[5005][5005],x;
void precalcDiv()
{
    for(long long i=2;i*i<=N;i++)
    {
        if(N%i==0)
            Div[++Div[0]]=i;
    }
    for(long long i=Div[0];i>=1;i--)
        if(Div[i]!=N/Div[i])
            Div[++Div[0]]=N/Div[i];
    Div[++Div[0]]=N;
}
long long binSearch(long long val)
{
    int left=1,right=Div[0],mid;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(Div[mid]<val)
        {
            left=mid+1;
        }
        if(Div[mid]>val)
            right=mid-1;
        if(Div[mid]==val)
            return mid;
    }
}
void Solve()
{
    for(int j=1;j<=Div[0];j++)
        A[0][j]=1;
    for(int i=1;i<=Div[0];i++)
    {
        int poz=1;
        for(int j=i;j>=1;j--)
        {
            A[i][j]=A[i][j+1];
            if(i==j)
                A[i][j]++;
            if(Div[i]%Div[j]==0 && i!=j)
            {
                while(Div[poz]<Div[i]/Div[j])
                    ++poz;
                A[i][j]+=A[poz][j];
            }
        }
    }

    g<<A[Div[0]][1]<<"\n";
    long long D=Div[0],first=1;
    while(K>0 && D>1)
    {
        while(Div[D]%Div[first]!=0)
            ++first;
        x=binSearch(Div[D]/Div[first]);
        if(K>A[x][first])
            K-=A[x][first],first++;
        else
        {
            g<<Div[first]<<" ";
            long long aux=Div[D];
            aux/=Div[first];
            D=binSearch(aux);
        }
    }
}
int main()
{
    f>>N>>K;
    precalcDiv();
    Solve();
    return 0;
}