ainta   10달 전

Convolution을 계산하는 문제를 FFT로 풀면 실수 오차 때문에 WA가 나는데,

소수로 나눈 나머지를 구할 수 있는 NTT 알고리즘이라는 것이 있다고 들었습니다.

하지만 소수 p가 2^k+1꼴의 소수가 아닌 이상 원시근을 구한 뒤에 어떻게 해야 하는지 잘 모르겠습니다.

NTT에 대해 설명해주시거나 잘 설명되어있는 링크를 주시면 감사하겠습니다. 도와주세요 ㅠ

댓글을 작성하려면 로그인해야 합니다.