Cómo resolver la pregunta de salvar a Scofield en SPOJ

Answer 1

leer (a, b, n)
mcm = mcm (a, b)
ciclo = mcm / a + mcm / b – 1

res_a = piso (n / ciclo) * lcm
res_b = piso (n / ciclo) * lcm

para i de 0 a n% ciclo
si (res_a + a <res_b + b)
res_a + = a;
más
res_b + = b;

imprimir max (res_a, res_b)

Explicación:

Es posible que algunas cosas no sean muy claras al principio, así que explique qué es cada variable.

ciclo contiene el número de múltiplos únicos de A y B en el rango [math] [0, mcm) [/ math]

Ej: Para A = 3 y B = 5 los múltiplos en el rango [math] [0, 15) [/ math] son: 0, 3, 5, 6, 9, 10, 12, 15, por lo tanto ciclo = 7

Permite llamar a la matriz de múltiplos únicos como mul .
mul = [math] [0, 3, 5, 6, 9, 10, 12] [/ math]

Así que el resultado se puede calcular de la siguiente manera:

[math] {res = mul [{n \% cycle}] + LCM * \ lfloor \ frac {n} {cycle} \ rfloor} [/ math]

Answer 2

Hint-LCM
Números totales antes de un múltiplo común de a y b = LCM (a, b) / a + LCM (a, b) / b -2
Por ejemplo si a = 2 & b = 5
MCM = 10

Total de No antes entre cualquier múltiplo común de 2 y 5 = 10/2 +10/5 -2 = 5
Es decir, 2,4,5,6,8 (total 5) y luego LCM 10.

Del mismo modo habrá 5 términos entre 10 y 20 y así sucesivamente.