Algoritmos y Demas

Buenos días a todos, les comparto el código que hicimos en clase:

/*
  Autor : Rodrigo Burgos Dominguez.
  Problema: Regional 2006 ACM Mexico, 
*/
# include <stdio.h>
# include <string.h>

# define MAX 1000000

int prime[MAX +1], nprime, hash[ 256], hashprime[ MAX + 1];
char criba[MAX+1], cad[MAX+1];

void update( int n, int oper ){
   int x, pt;
   for( x = 0; x < nprime && x <= n; x++){
      for( pt = prime[x] ; pt <= n ; pt *= prime[ x ])	
          hashprime[ x ] += ( n / pt ) * oper;
   }	
}

int abso( int a ){ return a < 0 ? -a: a; }

int potencia( int a, int b ){
  int res = 1;
  for( ; b > 0  ;  b-- ) res *= a;
  return res; 	
}


main(){
  int x, y, ncases, cases, res, pot, val, n;
  nprime = 0;
  for( x = 2; x <= MAX ; x++)
    if( criba[ x ] == 0 )
       for( y = x * 2, prime[ nprime++ ] = x ; y <= MAX ; y+= x) criba[y] = 1;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
  	scanf("%s", cad);
  	n = strlen(cad);
  	memset( hash, 0, sizeof( hash ));
  	memset( hashprime, 0, sizeof( hashprime));
  	for( x = n - 1; x >= 0 ; x-- ) hash[ cad[ x ] ]++;
  	update( n , 1 );
  	for( x = 'a' ; x <= 'z'; x++){
  	  update( hash[ x ] , -1);
  	}
  	res = 1;
  	for( x = 1; x < n; x++)
  	  if( prime[x] != 5 )
  	     res  = (res * potencia( prime[x], hashprime[ x ])) % 10;
  	pot = abso( hashprime[ 0 ] - hashprime[ 2 ]);
  	val = ( hashprime[0] < hashprime[2]) ? 5 : 2; 
  	res = (res * potencia( val, pot) ) % 10;
  	printf("%d\n", res);
  }
  return 0;	
}

Lo que vimos en clase, que son los primos como sacarlos con la criba de Eratóstenes, factorizar un numero, conteo rápido de primos en un Factorial, saber obtener el numero de ceros y el ultimo numero distinto de cero.

Aquí les dejo los problemas para que practiquen, necesito que los envíen a la uva para ver si están entendiendo , si tienen dudas envíenme un correo a rodrigo.burgos@gmail.com con sus respectivas dudas.

Problemas:

Prime Cuts
http://uva.onlinejudge.org/external/4/406.html

Goldbach’s Conjecture
http://uva.onlinejudge.org/external/5/543.html
nota: 6 <= n <= 1,000,000 utilizen un hash para ver si un numero es primo (pueden usar el arreglo de la criba ) y solo iterar los 78,000 primos.

recuerden que la lectura de este seria asi:

while( scanf("%d", &n) != EOF && n != 0 ){
…
}

Problem G: Simply Emirp
http://uva.onlinejudge.org/external/102/10235.html

Problem E – Prime Words
http://uva.onlinejudge.org/external/109/10924.html

Problem F: The primary problem.
http://uva.onlinejudge.org/external/109/10948.html

Factors and Factorials
http://uva.onlinejudge.org/external/1/160.html
Nota: utilicen la técnica de conteo que les enseñe, de ver cuantos dos , tres, cincos hay en un N factorial para resolver este problema. Lean bien la salida como se debe hacer, si tiene dudas me escriben sus dudas.

Product of digits
http://uva.onlinejudge.org/external/9/993.html

How many zeros and how many digits?
http://uva.onlinejudge.org/external/100/10061.html
Nota: Deben leer sobre lo logaritmos.

Divisors
http://uva.onlinejudge.org/external/2/294.html

Factorial Factors
http://uva.onlinejudge.org/external/8/884.html

I – Find Terrorists
http://uva.onlinejudge.org/external/12/1246.html

Problem D – Count the factors
http://uva.onlinejudge.org/external/106/10699.html

Twin Primes
http://uva.onlinejudge.org/external/103/10394.html

Almost Prime Numbers
http://uva.onlinejudge.org/external/105/10539.html
Nota: el valor hiigh < 10^12 , esto es muy grande, pero deben darse cuenta, que un almost prime es un no primo que es divisible por un solo primo esto quiere decir que un almost primer es de la forma P^2, P^3 … P^n, como el valor mas peque es p^2, si buscamos un primo que sea mas grade de un 1000,000 = 10^6, su cuadrado seria mayor 10^12 que es nuestro tope, entonces basta con tener todos los primos menores a 10^6.

Factorial Frequencies
http://uva.onlinejudge.org/external/3/324.html

Problem A – Prime Distance
http://uva.onlinejudge.org/external/101/10140.html

Just the Facts
http://uva.onlinejudge.org/external/5/568.html

Prime Factors
http://uva.onlinejudge.org/external/5/583.html

Problem D: GCD LCM
http://uva.onlinejudge.org/external/113/11388.html

Largest Prime Divisor
http://uva.onlinejudge.org/external/114/11466.html
el numero es menor o igual 14 digitos, esto quiere decir que con un nomero 10^7 es suficiente para saber el cual es el primo mas grande.

Problem C: Composite Prime
http://uva.onlinejudge.org/external/110/11086.html