Hints → https://atcoder.jp/contests/arc158/editorial/5987

---

Below, congruence modulo \(p\) is often denoted by an equal sign.

We will ignore the condition \(x < y < z\) by sorting the solution after finding it.

---

[1] A characteristic of the equality

\(x^i + y^i + z^i\) is a homogeneous polynomial of degree \(i\), that is, all terms have a degree of \(i\). Let \(F(x,y,z)\) and \(G(x,y,z)\) be the left-hand and right-hand sides of the given equation, and these are also homogeneous polynomials, which satisfy the following for any \(t,x,y,z\):

\(F(tx,ty,tz) = t^{3n+1}F(x,y,z)\), \(G(tx,ty,tz) = t^{3n}G(x,y,z)\).

---

[2] Solution

Here is a strategy to find a solution to the equation.

• Choose some \((a,b,c)\).
• Select \(t\) so that \((x,y,z) = (ta,tb,tc)\) satisfies the equation.

For a fixed \((a,b,c)\), the equation \(F(ta,tb,tc) = G(ta,tb,tc)\) is equivalent to \(t^{3n+1}F(a,b,c) = t^{3n}G(a,b,c)\). If \(F(a,b,c)\neq 0\) and \(G(a,b,c)\neq 0\), we can find a non-zero \(t\) satisfying this by \(t = G(a,b,c)/F(a,b,c)\). Thus, we can obtain a solution if we can choose \((a,b,c)\) so that all of the following conditions are satisfied:

• \(a,b,c\neq 0\),
• \(a\neq b, a\neq c, b\neq c\),
• \(a^i+b^i+c^i\neq 0\) for \(i \in \{1,n,2n,3n\}\).

Intuitively, if we randomly choose \((a,b,c)\), it may seem that \(a^i+b^i+c^i\) takes values between \(0\) and \(p-1\) roughly randomly and we have \(a^i+b^i+c^i=0\) with probability about \(1/p\). This is wrong, and there are \(n\) and \(p\) such that we have \(a^i+b^i+c^i=0\) with probability considerably larger than \(1/p\), but we will prove later in [3] that even in such a case the randomized algorithm succeeds with large enough probability.

Thus, the problem can be solved as follows.

Keep randomly choosing a triple of integers \((a,b,c)\) between \(1\) and \(p-1\) until the above conditions are satisfied. Then, use it to find a solution \((x,y,z) = (ta,tb,tc)\).

The expected number of random choices is \(O(1)\) as shown in [3], and each choice involves raising numbers to the \(n\)-th power, so the expected time complexity is \(O(\log n)\) per test case.

---

[3] Evaluation of the probability of success

Let us show the following lemma.

【Lemma】Let \(p\) be a prime number \(5\) or greater, and \(i\) be an integer. For integers \(a,b,c\) between \(1\) and \(p-1\) randomly chosen, the probability that \(a^i+b^i+c^i=0\) is at most \(1/4\).

Let \(S\) be the non-zero \(i\)-th powers, and \(m = |S|\). \(m\) divides \(p-1\), and for each \(s\in S\), there are exactly \(\frac{p-1}{m}\) numbers \(a\) such that \(a^i = s\).

When \(m\geq 4\), for a fixed \((a,b)\) there are exactly \(0\) or \(\frac{p-1}{m}\) numbers \(c\) such that \(a^i+b^i+c^i=0\), so our claim holds.

When \(m=1\), \(a^i+b^i+c^i\) always equals \(3\), which is not \(0\) since \(p\geq 5\). The case \(m=2\) is similar since \(a^i, b^i, c^i\in \{\pm 1\}\).

When \(m=3\), if we let \(S = \{s_1,s_2,s_3\}\), then \(s_i^3=1\), and \(s_1+s_2+s_3=0\). Since \(p\geq 5\), if \(s^3=1\) then \((-2s)^3\neq 1\), so if \(i\neq j\) then \(s_i+2s_j \neq 0\). Thus, we have \(a^i+b^i+c^i=0\) only if \(\{a^i, b^i, c^i\} = \{s_1,s_2,s_3\}\), which happens with probability \(\frac{6}{27}\).

Now the proof is complete.

---

From【Lemma】and some simple observations, for a triple of integers \((a,b,c)\) between \(1\) and \(p-1\) randomly chosen, the following holds.

• The probability that \(a=b\), \(a=c\), or \(b=c\) is \(O(1/p)\).
• The probability that \(a+b+c\) is \(O(1/p)\).
• The probability that \(a^n+b^n+c^n=0\) is at most \(1/4\).
• The probability that \(a^{2n}+b^{2n}+c^{2n}=0\) is at most \(1/4\).
• The probability that \(a^{3n}+b^{3n}+c^{3n}=0\) is at most \(1/4\).

Therefore, it has been proved that the randomized algorithm in [2] succeeds with probability at least \(1/4 - O(1/p)\).

---

(Japanese version has some more information.)