sphericalsun   1년 전

직접 BigInt type을 구현해서 풀어보려고 했으나..brute force로 하나씩 곱하는 게 무리가 갔는지 시간 초과가 나네요...간과한 테크닉이 있을까요..?

azruine   1년 전

fft의 비용은 O(nlogn)인데, 여기서 n이 크기가 큰 벡터의 길이입니다. 나이브하게 곱한다면 뒤로 가면 갈수록 결과값이 커지면서 n이 크게 올라가고, 이 때문에 시간이 오래 걸립니다.

그래서 곱셈을 나이브하게 하지 말고, 양 쪽의 크기를 좀 비슷하게 맞춰줄 필요가 있습니다.

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