Cod sursa(job #1733131)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 23 iulie 2016 17:38:50
Problema Descompuneri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#define MOD 666019
#define MAXU 4000
int dp[MAXU+1][MAXU+1], next[MAXU+1], u, lista[MOD];
long long val[MAXU+1];
inline int cauta(long long a){
    int p=lista[a%MOD];
    while((p)&&(val[p]!=a)) p=next[p];
    return p;
}
int main(){
    int k, i, j;
    long long n;
    FILE *fin, *fout;
    fin=fopen("desc.in", "r");
    fout=fopen("desc.out", "w");
    fscanf(fin, "%lld%d", &n, &k);
    i=2;
    while(i*(long long)i<=n){
        if(n%i==0){
            u++;
            val[u]=i;
            next[u]=lista[i%MOD];
            lista[i%MOD]=u;
        }
        i++;
    }
    while(i>0){
        if((i*(long long)i<n)&&(n%i==0)){
            u++;
            val[u]=n/i;
            next[u]=lista[(n/i)%MOD];
            lista[(n/i)%MOD]=u;
        }
        i--;
    }
    for(i=1; i<=u; i++){
        dp[i][i]=1;
        for(j=i-1; j>0; j--){
            dp[i][j]=dp[i][j+1];
            if(val[i]%val[j]==0) dp[i][j]+=dp[cauta(val[i]/val[j])][j];
        }
    }
    fprintf(fout, "%d\n", dp[u][1]);
    i=u;
    j=1;
    while(i>0){
        while(dp[i][j]-dp[i][j+1]<k){
            k-=dp[i][j]-dp[i][j+1];
            j++;
        }
        fprintf(fout, "%lld ", val[j]);
        i=cauta(val[i]/val[j]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}