oVeron

거듭제곱끼리의 곱셈은 차수의 덧셈과 같다. 여기서 차수는 \(k_i\)와 같으므로, FFT를 이용해 다항 방정식의 곱셈을 빠르게 계산하면 문제를 해결할 수 있다. \(k_i\)차의 계수를 1로 하는 방정식을 2개 만든다.예제 입력에서 \(k_i\)가  1, 3, 5이므로, \(1 * x^1 + 1 * x^3 + 1* x^5\)의 다항 방정식을 2개 만든다.두 다항 방정식을 곱해서 나온 방정식의 어떠한 차수의 계수가 1일 때, 그 차수가 \(d_i\)라면 \(d_i\)는 답이 될 수 있다.예를 들어 \(d_i\)가 4일 경우 \(x^1 * x^3 = x^4 (1 + 3 = 4)\)이므로 4는 답이 될 수 있다.#include using namespace std;typedef long long ll;type..

알고리즘/baekjoon 2024. 8. 11. 09:19