[BOJ] 5051번: Just A Few More Triangles!

https://www.acmicpc.net/problem/5051

Chinese Remainder Theorem을 풀려고 CRT로 분류된 문제를 봤는데 CRT로는 잘 모르겠고 FFT로 풀어냈습니다.

일단 a <= b 라는 조건은 무시하고 (a,b,c)의 쌍의 갯수를 구해봅시다. i = 1 to N-1에 대해 i의 제곱을 N으로 나눈 나머지를 구해 각 나머지가 몇 번 등장하는지를 확인합니다.(나머지가 k인게 rem[k]번 등장한다고 합시다.) 그러고나면 r1+r2=r3을 만족하는 r1,r2,r3에 대해 rem[r1]*rem[r2]*rem[r3]을 전부 더하면 됩니다. 문제는 이렇게 짜면 시간복잡도가 $O(N^2)$이 된다는 점입니다.

이제 식을 조금 변형해보겠습니다. 편의상 N = 5라고 가정하겠습니다.)

rem[0](rem[0]*rem[0]+rem[1]*rem[4]+rem[2]*rem[3]+rem[3]*rem[2]+rem[4]*rem[1]) +

rem[1](rem[0]*rem[1]+rem[1]*rem[0]+rem[2]*rem[4]+rem[3]*rem[3]+rem[4]*rem[2])+

rem[2](rem[0]*rem[2]+rem[1]*rem[1]+rem[2]*rem[0]+...)

+...

이런 꼴이 나오고 해당 식은 FFT로 $O(Nlg^2N)$ 에 계산할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/5051.cpp