Divisible o no#13059
Andrii y Taras están jugando el siguiente juego.
Dados dos enteros positivos y , donde es un número primo.
Primero, Andrii elige cualesquiera enteros positivos consecutivos a_1, a_2, \ldots, a_n. Es decir, a_1 \ge 1 y a_{i+1} = a_i + 1 para todo 1 \le i < n.
Luego Taras elige un subsegmento no vacío del arreglo .
Taras gana si la suma de los números en el subsegmento elegido es divisible por . En caso contrario, gana Andrii.
Determina quién gana con juego óptimo.
La única línea contiene dos enteros y (1 \le n, m \le 10^{18}).
Se garantiza que es primo.
Imprime Andrii si Andrii puede garantizar su victoria.
En caso contrario, imprime Taras.
Ejemplo 1
Ejemplo 2
En el primer ejemplo, entre cualesquiera enteros consecutivos siempre hay un número divisible por . Taras puede elegir un subsegmento que consista solo de este número, así que siempre puede ganar.
En el segundo ejemplo, Andrii puede elegir los números 1, 2, 3, 4. Las sumas de todos los subsegmentos no vacíos de este arreglo son 1, 2, 3, 4, 3, 5, 7, 6, 9 o . Ninguno de estos números es divisible por , así que Taras no puede ganar.
Subtarea ( puntos): n \le 20, m \le 20.
Subtarea ( puntos): n \le 2000, m \le 2000.
Subtarea ( puntos): Sin restricciones adicionales.