Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CIIC2013B - Enormes Olas

Problema B - Enormes Olas

Cuando no está estudiando algoritmos o programando estructuras de datos muy complejas, a Rafael le gusta surfear en las arenosas playas de su ciudad natal. Es realmente muy bueno (tal vez debería focalizarse más en la programación) y disfruta participar de competencias y eventos de surf. Le gustan especialmente las olas gigantes, que lo hacen sentir en paz consigo mismo mientras surfea y siente el océano.

Una ola se puede ver como una secuencia de enteros (estos enteros tienen que ver con complicadas fórmulas del surf y podemos simplemente asumir que serán dados). Hay dos conceptos muy importantes relacionados con las olas: longitud y magnitud. La longitud de una ola es el número de enteros en la secuencia. La magnitud de una ola se define como el máximo común divisor (mcd) de todos los números en la secuencia. Definimos máximo común divisor de un conjunto de enteros como el mayor entero positivo que divide a los números sin dejar resto. Por ejemplo, gcd(8,20) = 4, y gcd(15,5)=5

Rafael va a participar en el campeonato mundial del surfeo de la ola más grande. Afortunadamente, sabe exactamente cómo estará el agua durante el evento. Esto está dado por una secuencia de N enteros. Cualquier subsecuencia (intervalo contiguo de enteros) de esta secuencia es una ola. Como Rafael no puede surfear todas las olas, necesita encontrar la ola más larga para surfear. Sin embargo, hay un mínimo de magnitud de ola requerido, para asegurarse de que no pueda simplemente elegir toda la secuencia. Considerando, por ejemplo, que N=5, M=2 y que nos es dada la siguiente secuencia:

3 2 4 6 5

La mayor ola que tiene magntitud mínima 2 es la ola {2,4,6}, con longitud 3. Notar que mcd(2,4,6)=2, y luego esta ola tiene magnitud 2. Cualquier otra ola posible sería o bien más corta (una subsecuencia de menos de 3 enteros) o tendría una magnitud menor que lo que es requerido (por ejemplo, la ola {3,2,4,6,5} tiene magnitud 1).

¿Puedes ayudar a Rafael a encontrar la mayor ola que pueda surfear para que gane el campeonato?

El Problema

Dados dos enteros N y M y una secuencia de N enteros, representando la condición del agua, debes calcular la ola más larga con magnitud mínima M, esto es, la más larga subsecuencia de números contiguos para los que su máximo común divisor es mayor o igual a M.

Datos de entrada

La primera línea contiene dos enteros N (longitud de la secuencia de enteros dada) y M (magnitud mínima de una ola para ser considerada), separados por un único espacio.

La segunda línea contiene una secuencia que representa la condición del agua. Esto está dado por una secuencia de N enteros Vi, separados por un solo espacio, donde Vi es el i-ésimo entero de la secuencia.

Datos de salida

Una sola línea, conteniendo un entero que representa la longitud de la mayor ola que tiene magnitud mínima M.

Restricciones

Los siguientes límites son garantizados para todos los casos de prueba que sean usados para evaluar tu programa:

1 ≤ N ≤ 500 000       Número de enteros en la secuencia
1 ≤ M ≤ 230       Magnitud mínima de la ola
1 ≤ Vi ≤ 230       Máximo valor para un entero de la secuencia

Nota acerca de la evaluación

Para el conjunto de casos de prueba que valen el 25% de los puntos, siempre ocurre que N≤ 100.

Para el conjunto de casos de prueba que valen el 60% de los puntos, siempre ocurre que N≤5 000.

Entrada ejemplo 1

5 3
3 6 8 9 3

Salida ejemplo 1

2

Explicación de la entrada 1

Ambos {3,6} y {9,3} tienen magnitud 3. Todas las olas que incluyan el número 8 tendrán magnitud menor que 3 y luego la ola más larga que respeta la magnitud mínima requerida tiene longitud 2.

 

Entrada ejemplo 2

10 2
3 5 10 25 2 13 2 4 1 2

Salida ejemplo 2

3

Explicación de la entrada 2

La secuencia {5,10,25} tiene longitud 3 y magnitud 5. Como no hay una secuencia más larga con magnitud mayor o igual a 2, la ola más larga con la magnitud mínima requerida tiene longitud 3.



Adicionado por:Gabriel Rivera Safadi
Fecha:2016-06-07
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP CPP C++ 4.3.2 CPP14 JAVA
Fuente:CIIC

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.