Desafío en línea de Google para pasantías de verano 2021

El desafío en línea de Google 2020 para pasantías de verano 2021 se llevó a cabo el 26 de septiembre. Fue una prueba en línea de 60 minutos con 2 preguntas para codificar.

Primera pregunta: le dan una array A con N enteros. debe responder a consultas Q de los siguientes tipos.

Determine el conteo de números primos distintos que divide todos los números en un rango dado L a R. NOTA: 1 Indexación basada.

1 <=N,Q<= 10^5;

1 <= A[i] <= 10^5;

1 <= L <= R <= norte

Aporte: 

No of test cases
Array size i.e N
N array elements
No of Queries i.e Q
Q queries

Salida: Recuento de números primos distintos que divide todos los números en un rango dado para cada consulta

Entrada de muestra:  

1
6
4 6 3 18 36 54
3
1 2
3 6
4 6

Salida de muestra:

1
1
2

No recuerdo exactamente la segunda pregunta. Pero también se basó en arrays. Prepárese para preguntas de array basadas en consultas, algoritmo de MO, árbol de segmentos (si es posible) preguntas estándar como consultas de suma de rango, consultas de rango de actualización, etc.