Cod sursa(job #1814698)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 24 noiembrie 2016 13:00:54
Problema Factoriale Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <bitset>
#define DIM 101
using namespace std;
int n,i,j,d,p,k,k2,x,e,st,dr,mid;
int v[DIM],f[DIM];
bitset <DIM> ciur;
ifstream fin ("factoriale.in");
ofstream fout ("factoriale.out");

int main (){
// 48 = 2*2*2*2*3
    fin>>n>>k2;
    for (i=2;i<=100;i++){
        if (ciur[i] == 0){
            for (j=i+i;j<=100;j+=i)
                ciur[j] = 1;
            f[++k] = i;
        }
    }
    for (i=1;i<=n;i++){
        fin>>x;
        for (j=2;j<=x;j++){
            // descompunem in factori primi fiecare numar din factorila
            // si adaugam la exponent
            d = 1;
            p = j;
            while (p!=1 && f[d]*f[d] <= p){
                e = 0;
                while (p % f[d] == 0){
                    p /= f[d];
                    e++;
                }
                if (e != 0){
                    v[d] += e;
                }
                d++;
            }
            if (p!=1){
                // cautam pe ce pozitie se afla p in vectorul f
                st = 1;
                dr = k;
                while (st<=dr){
                    mid = (st+dr)/2;
                    if (f[mid] == p){
                        v[mid]++;
                        break;
                    }
                    else
                        if (f[mid] < p)
                            st = mid+1;
                        else
                            dr = mid-1;
                }
            }

        }
    }
    long long sol =  1;
    for (i=1;i<=k;i++){
        if (v[i]!=0 && v[i] < k2){
            // adunam la solutie f[i] la puterea k2-v[i]
            for (j=1;j<=k2-v[i];j++)
                sol *= f[i];
        }
    }
    fout<<sol;
    // exponentul trebuie sa fie k;


    return 0;
}