cho.shFFT Algorithm
정수 m과 k가 주어질 때, m을 법으로 하는 원시 2k제곱근을 하나 찾거나 존재하지 않으면 -1을 출력한다.
어려움8수학정수론구현분할 정복아직 제출이 없습니다시간 제한1.5초메모리 제한512 MB문제
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:
- 0 ≤ ω < m,
- ω2k ≡ 1 (mod m),
- ωp ≠ 1 (mod m) for all 0 < p < 2k.
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 ω.