Cod sursa(job #1728925)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 13 iulie 2016 20:57:47
Problema Descompuneri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<algorithm>
#define MAXD 4100
using namespace std;
int v[MAXD],dividers;
long long dp[MAXD][MAXD];
int BinarySearch(long long value){
    int left=1,right=dividers,middle;
    while(left<=right){
        middle=(left+right)/2;
        if(v[middle]==value)
            return middle;
        if(v[middle]<value)
            left=middle+1;
        else
            right=middle-1;
    }
    return -1;
}
int main(){
    freopen("desc.in","r",stdin);
    freopen("desc.out","w",stdout);
    long long n,k,i,j;
    scanf("%lld%lld",&n,&k);
    for(i=1;i*i<=n;i++)
        if(n%i==0){
            dividers++;
            v[dividers]=i;
            if(i*i!=n){
                dividers++;
                v[dividers]=n/i;
            }
        }
    sort(v+1,v+dividers+1);
    for(i=2;i<=dividers;i++){
        dp[i][i]=1;
        for(j=i-1;j>=2;j--){
            dp[i][j]+=dp[i][j+1];
            if(v[i]%v[j]==0&&v[i]/v[j]>=v[j])
                dp[i][j]+=dp[BinarySearch(v[i]/v[j])][j];
        }
    }
    printf("%d\n",dp[dividers][2]);
    i=dividers;
    j=2;
    while(i>=2){
        if(k>dp[i][j]-dp[i][j+1]){
            k=k-(dp[i][j]-dp[i][j+1]);
            j++;
        }
        else{
            printf("%lld ",v[j]);
            i=BinarySearch(v[i]/v[j]);
        }
    }
    return 0;
}