Page 1 of 1

2649 - Square Factory

Posted: Fri Nov 29, 2013 3:53 pm
by ymondelo20

Re: 2649 - Square Factory

Posted: Mon Dec 02, 2013 5:33 pm
by facug91
Hola, para resolver este problema un amigo encontró la fórmula Image donde el a1 sería 1 (el primer elemento) y r sería 4.
Cuando lo escribimos con exponenciación rápida modular, en los casos ejemplos endaba, entonces lo subimos y nos dio wrong answer. Entramos en el datagen y nos dimos cuenta que para algunos casos funciona y para otros no. No entendíamos por qué, y al final nos dimos cuenta que aveces hace el módulo de 1000003, y después divide por 3 (r - 1 = 4 - 1 = 3), y ahí da mal el resultado. No sé si se pueden postear códigos acá por eso no lo hago (es mi primer mensaje en el foro).
Nuestro problema es que no sabemos cómo resolver esto, porque no se puede poner la división por 3 adentro de la función de exponencición, pero afuera da mal el resultado... cómo podemos hacer para solucionar eso? O es por otro lado la solución?

Re: 2649 - Square Factory

Posted: Wed Dec 04, 2013 2:36 pm
by ymondelo20
Puedes postear la sección del código que te interesa...
Además, no es una solución aceptada.

Re: 2649 - Square Factory

Posted: Thu Dec 05, 2013 1:19 pm
by facug91
Este es mi código (sin contar los includes):

Code: Select all

#define square(x) ((x) * (x))
#define tint long long int
#define mod 1000003

using namespace std;

int c;
tint n;

int bigmod (tint p) {
	if (p == 0) {
		return 1;
	} else if (p % 2 == 0) {
		return square(bigmod(p/2)) % mod;
	} else {
		return (4 * bigmod(p-1) % mod);
	}
}

int main() {
	cin>>c;
	
	for (;c--;) {
		cin>>n;
		printf("%d\n",(bigmod(n+1)-1)/3);
	}
	
    return 0;
}
El tema es que como el número es muy grande, en la exponenciación (osea, la función bigmod), además de elevar el 4 a la potencia 'n+1', va haciendo el mod 1000003, y cuando vuelve y divide por 3, muchas veces da mal el resultado. Pero no sé cómo arreglar eso, o si en realidad estoy encarando mal el problema.

Re: 2649 - Square Factory

Posted: Thu Dec 05, 2013 3:20 pm
by rvargas
¿No sera un problema que solo le estás aplicando modulo solo a la potencia?

Re: 2649 - Square Factory

Posted: Thu Dec 05, 2013 9:41 pm
by facug91
No, por ejemplo, si calculo 4^9 debería darme 1048576, lo que dividido 3 me da 349525 (redondeado), resultado que es correcto. Pero en mi resolución, como en la exponenciación hago el módulo de todos los resultado, me devuelve 48573, que dividido 3 me da 16191. El problema está en que tengo que dividir el resultado por 3, y no sé cómo hacer eso usando módulo antes...

Aclaración: hacer el módulo del resultado dividido 3 no tendría sentido, porque el número va a ser sí o sí menor que el resultado de la función bigmod, que es donde aplico el módulo.

Re: 2649 - Square Factory

Posted: Sat May 09, 2015 5:13 pm
by HaZard
¿el tamaño del código no puede exceder los 128 bytes? por favor arreglen esto...

Re: 2649 - Square Factory

Posted: Tue Jun 02, 2015 9:51 pm
by HaZard
ahora me aparece que el tamaño del codigo puede llegar hasta 16 Kb, pero al enviar mi solucion me dice "The source code is too long", que puede estar pasando?

Re: 2649 - Square Factory

Posted: Wed Jun 03, 2015 8:42 pm
by ymondelo20
HaZard wrote:ahora me aparece que el tamaño del codigo puede llegar hasta 16 Kb, pero al enviar mi solucion me dice "The source code is too long", que puede estar pasando?
Ya lo he corregido.
Saludos.