문제

계수가 0 또는 1로만 이루어지는 특수한 다항식들의 집합에 대해 생각해보자.

이 집합의 두 다항식을 더하는 방법은 다음과 같다.

• 우선, 두 다항식을 더한다.
• 결과 다항식의 각 계수를 2로 나눈 나머지를 각각의 계수에 대입한다.

이때, (0 + 0) mod 2 = 0, (0 + 1) mod 2 = 1, (1 + 0) mod 2 = 1, and (1 + 1) mod 2 = 0 이므로

결국 결과 다항식의 각 차수의 계수는 더하고자 했던 두 다항식의 계수에 대한 XOR 연산의 결과가 된다.

(x ⁶ + x⁴ + x² + x + 1) + (x⁷ + x + 1) = x⁷ + x⁶ + x⁴ + x²

이제 뺄셈을 정의하는데, 뺄셈의 경우에도 덧셈과 같이 (0 - 0) mod 2 = 0, (0 - 1) mod 2 = 1, (1 - 0) mod 2 = 1, and (1 - 1) mod 2 = 0 이므로
덧셈과 뺄셈은 이 다항식들의 집합에 대해 동일한 의미를 지닌다. (계수 간의 XOR 연산이 새 다항식의 계수가 됨)

예시는 다음과 같다.

(x ⁶ + x⁴ + x² + x + 1) - (x⁷ + x + 1) = x⁷ + x⁶ + x⁴ + x²

다음으로 곱셈을 정의하는데, 곱셈 또한 일반적인 다항식 간의 곱셈 연산을 한 뒤 각각의 계수를 2로 나눈 나머지를 취하면 된다.

(x ⁶ + x⁴ + x² + x + 1) (x⁷+ x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1

두 다항식 f(x)와 g(x)의 곱을 h(x)로 나눈 나머지는 f(x)와 g(x)를 위와 같은 방법으로 곱한 뒤, h(x)로 나눈 나머지가 된다.

(x ⁶ + x⁴ + x² + x + 1) (x⁷ + x + 1) modulo (x⁸ + x⁴ + x³ + x + 1) = x⁷ + x⁶ + 1

어떤 다항식의 최고차항의 차수를 degree, 줄여서 d라 하면, f(x), g(x), h(x)의 계수가 0 또는 1이므로 각 다항식은 정수 d+1과 길이 d+1인 비트스트링의 쌍으로 유일하게 표기할 수 있다. 다항식의 차수는 1000보다 작다.

예를 들어 x ⁷ + x⁶ + 1은 다음과 같이 표기된다.

8 1 1 0 0 0 0 0 1

이때, 8은 총 비트의 개수이며, 최고차항의 차수(7) + 1이다.

이제 위에서 설명한 성질을 만족하는 세 다항식 f(x), g(x), h(x)가 설명한 형식대로 주어지면 f(x)g(x) modulo h(x)를 계산하면 된다.

===============================================================

위가 문제 내용인데

'나머지 연산'의 정의를 모르겠습니다. 일반 다항식 나누기랑 연관있나 싶어서 울프람알파에 modulo 해봤는데 전혀 틀리게 나오고..

아마 위에서 더하기, 뺄셈을 친절하게 정의해준 것과 연관이 있을 것 같은데 어떤 점이 연관있는지를 잘 모르겠습니다.

조언 부탁드리겠습니다!