Cod sursa(job #585750)

Utilizator AndreyPAndrei Poenaru AndreyP Data 30 aprilie 2011 11:37:54
Problema NumMst Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.75 kb
#include <cstdio>
#include <cmath>
#define ll long long

int n,d;
double n1,d1;

inline double get(int k) {
    double k1 = (double)k;
    int aux = n%k;
    if(aux==0)
        aux = n/k;
    return (k1*log(d1) + (k1-1.000000)*log((double)(n/k)) + log((double)aux));
}

inline int cmmdc(int a,int b) {
    int r;
    while(b) {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

inline ll cmmmc(int x,int y) {
    if(y==0)
        return ((ll)x);
    return (((ll)(x/cmmdc(x,y)))*((ll)y));
}

int main() {
    freopen("nummst.in","r",stdin);
    freopen("nummst.out","w",stdout);

    scanf("%d",&n);
    for(d=n-1; d>0 && n%d!=0; --d)
        ;
    //printf("%d ",d);
    n /= d;
   /* for(int i=1; i<n; ++i)
        printf("%d ",d);
    printf("%d\n",d);
    return 0;*/

    ll aux=(ll)d,aux1;
    int k=n;
    for(int i=2; i<n; ++i) {
        aux1 = (ll)d*((ll)(n/i))*((ll)n%i);
        if(aux1>aux) {
            aux = aux1;
             k =i;
        }
    }

    //n1 = (double)n;
    //d1 = (double)d;

    int p=2,u=n,m;

   /* while(p+16<u) {
        m = (p+u)>>1;

        if(get(m-1)<=get(m))
            p = m;
        else
            u = m-1;
    }*/

    /*ll aux=cmmmc(d*(n/p),d*(n%p)),aux1;
    int k=p;
    for(int i=p+1; i<=u; ++i) {
        aux1 = cmmmc(d*(n/i),d*(n%i));
        if(aux1>aux) {
            k = i;
            aux = aux1;
        }
    }*/
    /*double aux=get(p),aux1;
    int k=p;
    for(int i=p+1; i<=u; ++i) {
        aux1 = get(i);
        if(aux1>aux) {
            aux = aux1;
            k = i;
        }
    }*/

    //printf("%lld\n",((ll)d)*cmmmc(n/k,n%k));

    p = (n/k)*d;
    for(int i=1; i<k; ++i)
        printf("%d ",p);
    if(n%k==0)
        printf("%d\n",p);
    else
        printf("%d\n",d*(n%k));
    return 0;
}