Cod sursa(job #778598)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 15 august 2012 01:46:16
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

long long n;
int i,j;
int t;
int k,nrdiv;
vector<long long> v;
int m[3001][3001];

int main()
{freopen("desc.in","r",stdin);
freopen("desc.out","w",stdout);
scanf("%d %d",&n,&k);
int sqrtn = (int) sqrt((double) n);

for(i=2; i<sqrtn; i++)
  if(n%i==0)
  {nrdiv+=2;  v.push_back(i);   
   v.push_back((long long)(n/i));} 
  
if(sqrtn>1 && n%sqrtn==0)
  {nrdiv++;  v.push_back(sqrtn);
   if(n/sqrtn!=sqrtn)
      {nrdiv++;  v.push_back(n/sqrtn);}
  }   
      
nrdiv++;  
v.push_back(n);
v.push_back(0);
sort(v.begin(),v.end());    

  
m[1][1]=1;    
for(i=2; i<=nrdiv; i++)
  {m[i][i]=1;
   for(j=i-1; j>=1; j--)
    {m[i][j]=m[i][j+1];
     if(v[i]%v[j]==0)
     {t=1;
      while(v[t]<v[i]/v[j])   t++;
      m[i][j]+=m[t][j];
      }
    }
  }        
  
printf("%d\n",m[nrdiv][1]);

i=nrdiv;
j=1;

while(n>1)
{if(m[i][j]-m[i][j+1]<k)
   {k=k-m[i][j]+m[i][j+1];
    j++;}
 else
   {
    printf("%d ",v[j]);
    n=n/v[j];
    if(n!=1)
       while(v[i]>n)  i--;
   }     
}
return 0;}