Cod sursa(job #971777)

Utilizator mihai995mihai995 mihai995 Data 10 iulie 2013 01:49:05
Problema NumMst Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
using namespace std;

const int N = 10001;

int v[N];

ifstream in("nummst.in");
ofstream out("nummst.out");

inline int cmmdc(int a, int b){
    return b == 0 ? a : cmmdc(b, a % b);
}

inline int cmmmc(int a, int b){
    return a / cmmdc(a, b) * b;
}

int factor(int n){
    int val = 2;
    while (n % val) ++val;

    return val;
}

void solve(int v[], int n){
    v[0] = v[1] = 1;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j < i ; j++)
            v[i] = max(v[i], cmmmc(v[j], i - j));
}

void print(int v[], int poz, int F){
    while (poz){
        int next = poz;

        while (v[poz] != cmmmc(v[next], poz - next))
            next--;

        out << (poz - next) * F << " ";
        poz = next;
    }

    out << "\n";
}

int main(){
    int F, n;

    in >> n;
    F = factor(n);

    solve(v, F);
    print(v, F, n / F);

    return 0;
}