Hide

Dulmál

This time around you have been tasked with the job of creating a cipher for secret transmissions. Why? I suppose I could tell you, but you have to promise you’ll tell no one! Beneath The University of Iceland is a secret society of cavedwellers that have true control over the university. A secret council that stays hidden so no one can disturb their schemes. They recently built a supercomputer out of several hundred GPUs that they somehow acquired. But now comes the problem. Now they have to transmit data from this supercomputer through The University of Iceland’s wifi and the lizard people dwelling in the caves want to be completely sure that no one can read the data even if they were to somehow intercept it, no one but them selves of course. To solve this problem, one of the lizards suggested that they agree on an alphabet along with one secret number and then communicate via a series of numbers. A number would then be decoded into a letter by raising the secret number to that power and then take the remainder when the result is divided by the number of letters in the alphabet plus one. If the remainder were $r$ the resulting letter would be the $r$-th letter in the alphabet (counting from one). The other lizards quite liked this suggestion but weren’t convinced it’d work. They weren’t sure if all the letters could be encoded such that this decoding method would work. The lizard suggesting this cipher wasn’t able to prove that all letters could be encoded in this fashion. That’s where you come in! You have to deduce if a given secret number is valid. The lizards are very computer science oriented so they of course don’t just want a one off answer but a program that can solve that problem in general, that way they don’t need to ask for help again later.

Input

The only line in the input contains two integers $2 \leq n \leq 10^9$ and $1 \leq k \leq n$ where $n$ is the number of letters in the alphabet and $k$ is the chosen secret number.

Output

One line saying ‘Gild leynitala!’ (‘Valid secret number’ in Icelandic) if the secret number is valid, ‘Ogild leynitala!’ (‘Invalid secret number’ in Icelandic) otherwise.

Sample Input 1 Sample Output 1
4 3
Gild leynitala!
Sample Input 2 Sample Output 2
5 3
Ogild leynitala!
Sample Input 3 Sample Output 3
6 2
Ogild leynitala!
CPU Time limit 2 seconds
Memory limit 1024 MB
Languages English, Íslenska
Authors
Bergur Snorrason and Atli Fannar Franklín
Source Forritunarkeppni Háskóla Íslands 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in