Remover um Único Elemento 2
Dada uma lista de
n inteiros, pretende-se remover um desses inteiros de forma que o produto resultante, ao ser calculado em módulo m, seja igual a p. Formalmente, se o índice do elemento removido for r, então:O programa deve encontrar o índice desse elemento ou imprimir
Impossible se não existir um elemento que satisfaça a condição.Entrada
A primeira linha da entrada contém 3 inteiros
n (1 ≤ n ≤ 10^5), m (1 ≤ m ≤ 10^9) e p (0 ≤ s < m).A segunda linha contém
n inteiros separados por espaço: a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9).Saída
Se não existir tal número, o programa deve imprimir
Impossible. Caso contrário, deve imprimir o menor índice desse elemento na lista (a contagem de índices começa em 1).Exemplos
Entrada | Saída |
3 8 5
5 0 9 | 2 |
3 8 5
5 10 7 | Impossible |
Explicação
- 5 * 9 = 45 ⇒ 45 mod 8 = 5. Para obter esse resultado, podemos remover o elemento 0, que está na posição 2, pois então o produto restante é 5 (mod 8).
- Não é possível remover nenhum dos elementos para que o produto do array resultante, em módulo 8, seja igual a 5.
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB