페르마의 마지막 정리

페르마의 마지막 정리는 다음과 같다.

$\nexists (x, y, z) \in (\mathbb{Z}\setminus\{0\})^3 \quad \text{s.t.} \quad x^n + y^n = z^n \ (n \ge 3, n \in \mathbb{Z}, xyz \ne 0)$

출처: 페이스북 수학 갤러리

유학을 꿈꾸는 창호는 위 그림에서처럼 서학을 믿고 있다. 그래서 자신이 페르마의 마지막 정리를 넘어 '창호의 마지막 정리'를 만들었다고 자랑한다. 먼저 $2$ 이상의 정수 $k$를 소인수분해했을 때 나오는 서로 다른 소수들의 집합을 $k$의 소수 집합이라고 하고 $\mathbb{p}(k)$로 쓴다. $1$은 소인수분해할 수 없으므로 $\mathbb{p}(1) = \emptyset$으로 둔다. 즉, $k = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ($p_i$는 서로 다른 소수이고 $e_i \ge 1$인 정수)이면 $\mathbb{p}(k) = \{p_1, p_2, \cdots, p_t\}$이다. 창호의 마지막 정리는 다음과 같다.

음이 아닌 홀수 $n$과 $0$이 아닌 정수 $x$, $y$에 대하여 $x + y \ne 0$이라고 하자. 어떤 1 이상의 정수 $z$가 존재해 $\mathbb{p}(z) \cap \mathbb{p}(\lvert x\rvert) = \emptyset$, $\mathbb{p}(z) \cap \mathbb{p}(\lvert y\rvert) = \emptyset$, $\mathbb{p}(z) \subseteq \mathbb{p}(\lvert x+y\rvert)$라면, 모든 음이 아닌 정수 $m$에 대하여 $\lvert x^n + y^n\rvert$는 $z^m$의 배수가 될 수 없다.

동우는 이 명제에 반례가 상당히 많다는 것을 발견한다. $n$, $x$, $y$, $m$이 주어졌을 때 위 명제를 만족하지 않는 $z^m$의 개수와 합을 구하자. 즉, $\mathbb{p}(z) \cap \mathbb{p}(\lvert x\rvert) = \emptyset$, $\mathbb{p}(z) \cap \mathbb{p}(\lvert y\rvert) = \emptyset$, $\mathbb{p}(z) \subseteq \mathbb{p}(\lvert x+y\rvert)$를 만족하면서 $\lvert x^n + y^n\rvert$가 $z^m$의 배수가 되는 $z^m$의 개수와 합을 구하면 된다.

첫 번째 줄에 음이 아닌 홀수 $n$ ($1 \le n \le 10^{18}$, $n \equiv 1 \pmod{2}$), $0$이 아닌 정수 $x$와 $y$ ($1 \le \lvert x\rvert, \lvert y\rvert \le 10^{18}$, $x + y \ne 0$), 정수 $m$ ($1 \le m \le 10^{18}$)이 공백으로 구분되어 주어진다.

주어진 $n$, $x$, $y$, $m$에 대해 $\mathbb{p}(z) \cap \mathbb{p}(\lvert x\rvert) = \emptyset$, $\mathbb{p}(z) \cap \mathbb{p}(\lvert y\rvert) = \emptyset$, $\mathbb{p}(z) \subseteq \mathbb{p}(\lvert x+y\rvert)$를 만족하면서 $\lvert x^n + y^n\rvert$가 $z^m$의 배수가 되는 $z^m$의 개수와 합을 구한다. 두 값을 각각 $1\,000\,000\,007$로 나눈 나머지를 공백으로 구분하여 출력한다.