|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1.5 초||512 MB||94||14||6||23.077%|
When I want to apply FFT algorithm to polynomial of degree less than 2k in modular arithmetics, I have to find ω — a primitive 2k-th root of unity.
Formally, for two given integers m and k, I should find any integer ω such that:
In this task, I ask you to find ω for me, or determine that it does not exist. Since we talk about application of FFT, I’ve set some reasonable limitations for k: for smaller k naive polynomial multiplication is fine, and for larger k FFT takes more than 1 second (we are competitive programmers after all).
The only line of input contains two integers m and k (2 ≤ m ≤ 4 · 1018, 15 ≤ k ≤ 23).
Print any ω satisfying the criteria, or print −1 if there is no such ω.