[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] divisor



On Mon, Jun 20, 2005 at 10:55:04PM -0300, fgb1 wrote:
> Pessoal, preciso de ajuda nessa:
> 
> Um fator de 2^33 - 2^19 - 2^17 -1, entre 1000 e 5000 é:
> a) 1993
> b) 1992
> c) 1983
> d) 1982
> e) 1972

2^33 - 2^19 - 2^17 -1 =  8589279231 = 3^3 * 13 * 661 * 37021.

Com isto é fácil verificar que o único divisor entre 1000 e 5000
é 1983 = 3*661.

Esta questão é perfeitamente viável no braço mesmo sem calculadora.
Calcular que 2^33 - 2^19 - 2^17 -1 =  8589279231 deve tomar perto
de 1 minuto se você souber que 2^16 = 65536 (faça 2^17 = 2*2^16,
2^19 = 4*2^17, 2^33 = 2^16*2^17) e as 5 divisões com resto
também não demoram tanto assim.

Talvez exista uma solução esperta mas eu não estou vendo.

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================