Cod sursa(job #137389)

Utilizator FlorinC1996Florin C FlorinC1996 Data 17 februarie 2008 11:53:19
Problema Factoriale Scor 40
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasa a 9-a Marime 1.76 kb
#include<stdio.h>
#include<math.h>
//int v[101],prime[101], exp[101], res[101],exponent;
//long  REZULTAT;
int verifica(int i)
{
int d,lim;
if(i%2==0 &&i!=2)
return 0; 
lim=sqrt(i);
for(d=3;d<=lim;d+=2)
if(i%d==0)
	return 0;
return 1;
}
int main()
{
int v[101],prime[101], exp[101], res[101]; //, exponent;
long long REZULTAT;
int n,k,i,max=-1,u=0, xgen, prodp, putere,j;
freopen("factoriale.in","r",stdin);
freopen("factoriale.out","w",stdout);
scanf("%d%d",&n,&k);
// aici se calculeaza max = max de x_i
for(i=1;i<=n;i++)
	{
	scanf("%d",&v[i]);
	if(v[i]>max)
		max=v[i];
	}
        // aici se calculeaza numerele prime mai mici decat max
for(i=2;i<=max;i++)
	if(verifica(i))
		prime[++u]=i;

	// aici se calculeaza puterea exp_i = suma puterilor lui p_i in x_kaii factoriali
	//exponent = 0;
	for (i = 1; i <= u; i++)
	{
		exp[i] = 0;
		for(j = 1; j <=n ; j++)
                {
			prodp = prime[i];
			xgen = v[j];
			while  (xgen /prodp)
			{
				exp[i]+= xgen/prodp;
                                prodp *= prime[i];
                        }
                }
	}

	// aici calculam res_i : cat mai trebuie pentru fiecare exp_i ca sa fie multiplu de k
	// adica  REZULTAT = produs de p_i ^ res_i , care inmultit cu produsul factorialelor
	// sa fie putere k perfecta
	for (i = 1; i <= u ; i++)
	{
	       if ( exp[i]% k)
	       {
			res[i] = k - ( exp[i]  % k );
               }
	       else
	       {
			res[i] = 0;
	       }	 
	}

	// aici calculam REZULTAT = produs de p_i la puterea res_i
	REZULTAT = 1;
	for (i = 1; i <= u ; i++)
	{      if (res[i] > 0)
		{
			for (j = 1; j <= res[i] ; j++)
			{
				REZULTAT *=  prime[i];
                        }
                }
	}

printf("%lld",REZULTAT);
return 0;
}