Cod sursa(job #963711)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 18 iunie 2013 14:59:49
Problema Factoriale Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
using namespace std;

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

bool ciur[110];
int N, k, v[110], maax;
long long sol=1;


void make_ciur()
{
    int i, j;
    for (i=2; i<=105; ++i)
        if (ciur[i] == 0)
            for (j=i*i; j<=105; j+=i)
                ciur[j] = 1;
}

void fact(int nr)
{
    int i;
    for (i=2; i<105; ++i)
        if (ciur[i]==0 && nr%i==0)
        {
            while (nr%i == 0)
            {
                v[i]++;
                nr /= i;
            }
            if (i > maax)
                maax = i;
            if (nr == 1)
                break;
        }
}

long long putere(int nr, int p)
{
    if (p == 0)
        return 1;
    if (p == 1)
        return nr;
    int x = putere(nr, p/2);
    if (p%2 == 0)
        return x*x;
    else
        return x*x*nr;
}

int main()
{
    make_ciur();
    int i, j, nr;
    fin >> N >> k;
    for (i=0; i<N; ++i)
    {
        fin >> nr;
        if (nr != 1)
            for (j=2; j<=nr; ++j)
                fact(j);
    }

    for (i=2; i<=maax; ++i)
        if (ciur[i]==0 && v[i]!=0)
            sol *= putere(i, v[i]%k);

    fout << sol;

    fin.close();
    fout.close();

    return 0;
}