Cod sursa(job #2413364)

Utilizator osiaccrCristian Osiac osiaccr Data 23 aprilie 2019 12:42:10
Problema Factoriale Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <bits/stdc++.h>
#define DEF 110
#define DEFPRIMES 30

using namespace std;

struct Huge {
    int v[1000];

    Huge () {
        v[0] = 1;
        v[1] = 1;
    }

    void operator*= (int x) {
        int t = 0;

        for (int i = 1; i <= v[0]; ++ i) {
            v[i] = v[i] * x + t;
            t = v[i] / 10;
            v[i] %= 10;
        }

        while (t) {
            v[++ v[0]] = t % 10;
            t /= 10;
        }
    }

};

ifstream fin ("factoriale.in");
ofstream fout ("factoriale.out");

int n, k;

Huge sol;

int ciur[DEF], M[DEFPRIMES];

int D[DEF][DEFPRIMES];

vector < int > Primes;

int main () {

    Primes.push_back (0);

    for (int i = 2; i <= 100; ++ i) {
        if (ciur[i] == 0) {
            Primes.push_back (i);
            for (int j = i + i; j <= 100; j += i) {
                ciur[j] = 1;
            }
        }
    }

    for (int i = 2; i <= 100; ++ i) {
        int x = i;
        for (int j = 1; j < Primes.size (); ++ j) {
            D[i][j] += D[i - 1][j];
            while (x % Primes[j] == 0) {
                ++ D[i][j];
                x /= Primes[j];
            }
        }
    }

    fin >> n >> k;

    for (int i = 1; i <= n; ++ i) {
        int x;
        fin >> x;

        for (int j = 1; j < Primes.size (); ++ j) {
            M[j] += D[x][j];
        }
    }

    for (int i = 1; i < Primes.size (); ++ i) {
        if (M[i] != 0) {
            if (M[i] < k) {
                while (M[i] < k) {
                    sol *= Primes[i];
                    ++ M[i];
                }
            }
            else {
                while (M[i] % k != 0) {
                    sol *= Primes[i];
                    ++ M[i];
                }
            }
        }
    }

    for (int i = sol.v[0]; i >= 1; -- i) {
        fout << sol.v[i];
    }


    return 0;
}