P14858 [ICPC 2021 Yokohama R] It' s Surely Complex

如你所知，复数通常表示为实部与虚部之和。$3 + 2i$ 就是这样一个例子，其中 $3$ 是实部，$2$ 是虚部，$i$ 是虚数单位。 给定一个质数 $p$ 和一个正整数 $n$，你为本题编写的程序应输出所有满足以下条件的复数的乘积。 - 实部和虚部均为小于或等于 $n$ 的非负整数。 - 实部和虚部中至少有一个不是 $p$ 的倍数。 例如，当 $p = 3$ 且 $n = 1$ 时，满足条件的复数是 $1$ ($= 1 + 0i$)、$i$ ($= 0 + 1i$) 和 $1 + i$ ($= 1 + 1i$)，这些数的乘积，即 $1 \times i \times (1 + i)$，等于 $-1 + i$。

输入由单个测试用例组成，格式如下。 $$p\ n$$ $p$ 是一个小于 $5 \times 10^5$ 的质数。$n$ 是一个小于或等于 $10^{18}$ 的正整数。

在一行中输出两个整数，用一个空格分隔。当满足给定条件的所有复数的乘积为 $a + bi$ 时，第一个和第二个整数应分别为 $a \bmod p$ 和 $b \bmod p$。这里，$x \bmod y$ 表示介于 $0$ 到 $y-1$ 之间（含）的整数 $z$，使得 $x - z$ 能被 $y$ 整除。 如题目描述部分所示，当 $p = 3$ 且 $n = 1$ 时，要计算的乘积是 $-1 + i$。然而，由于 $-1 \bmod 3 = 2$，因此在样例输出 1 中显示的是 $2$ 和 $1$。