Official

D - Equation Editorial by maspy

ヒント → https://atcoder.jp/contests/arc158/editorial/5901

以下の解説で，多くの場面で \(\pmod{p}\) での合同を単に等号で表すこととします．

条件 \(x < y < z\) については，単に解を求めてからソートすればよいので，以下 \(x,y,z\) の大小関係に関する議論は省略します．

[1] 方程式の特徴

\(x^i + y^i + z^i\) という式には，すべての項の次数が \(i\) であるという特徴があり，このような式は \(i\) 次の同次式 あるいは斉次式などといいます．本問題の左辺を \(F(x,y,z)\)，右辺を \(G(x,y,z)\) とすれば，これらも同次式で，任意の \(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] 解法

本問題の方程式の解を求める戦略として，次の方法を考えます．

  • \((a,b,c)\) を適当にとる．
  • \(t\) を上手くとって，\((x,y,z) = (ta,tb,tc)\) が方程式を満たすようにする．

\((a,b,c)\) を固定すれば，\(F(ta,tb,tc) = G(ta,tb,tc)\) は \(t^{3n+1}F(a,b,c) = t^{3n}G(a,b,c)\) と同値になります．もし \(F(a,b,c)\neq 0\) かつ \(G(a,b,c)\neq 0\) であれば，これを満たす \(0\) でない \(t\) を \(t = G(a,b,c)/F(a,b,c)\) により求めることができます．したがって，\((a,b,c)\) を以下の条件がすべて成り立つようにとることができれば解を得ることができます．

  • \(a,b,c\neq 0\)
  • \(a\neq b, a\neq c, b\neq c\)
  • \(i \in \{1,n,2n,3n\}\) に対して \(a^i+b^i+c^i\neq 0\)

直感的には，\((a,b,c)\) を乱択すれば，\(a^i+b^i+c^i\) が \(0\) 以上 \(p-1\) 以下の値をおおよそランダムにとり，\(a^i+b^i+c^i=0\) となってしまう確率は \(1/p\) 程度だと考えるかもしれません．これは誤りで，\(1/p\) よりもかなり大きな確率で \(a^i+b^i+c^i=0\) となってしまうような \(n, p\) は存在するのですが，そのような場合でも乱択の成功確率が十分高いことを以下の [3] で証明します．

したがって，本問は次のように解くことができます：

\(1\) 以上 \(p-1\) 以下の整数の組 \((a,b,c)\) を，上述の条件を満たすまで乱択し続ける．条件を満たしたらそこから解 \((x,y,z) = (ta,tb,tc)\) を求める．

この解法では乱択のやり直す回数の期待値が [3] で示す通り \(O(1)\) で，乱択するたびに \(n\) 乗計算を行うため，テストケースごとの期待時間計算量は \(O(\log n)\) 時間となります．

[3] 乱択の成功確率の評価

次の補題を示します：

【補題】 \(p\) を \(5\) 以上の素数とし，\(i\) を整数とする．\(1\) 以上 \(p-1\) 以下の整数 \(a,b,c\) を乱択するとき，\(a^i+b^i+c^i=0\) となる確率は \(1/4\) 以下である．

\(S\) を \(0\) でない \(i\) 乗数全体とし，\(m = |S|\) とします．\(m\) は \(p-1\) の約数で，各 \(s\in S\) に対して \(a^i = s\) となる \(a\) がちょうど \(\frac{p-1}{m}\) 個あります．

\(m\geq 4\) のときには，\((a,b)\) を固定したとき \(a^i+b^i+c^i=0\) となる \(c\) が \(0\) 個または \(\frac{p-1}{m}\) 個なのでよいです．

\(m=1\) のときは \(a^i+b^i+c^i\) は常に \(3\) に等しく，\(p\geq 5\) よりこれは \(0\) にならないのでよいです．\(m=2\) のときも \(a^i, b^i, c^i\in \{\pm 1\}\) より同様です．

\(m=3\) のとき，\(S = \{s_1,s_2,s_3\}\) とすると，\(s_i^3=1\) であり，\(s_1+s_2+s_3=0\) が成り立ちます．\(p\geq 5\) より \(s^3=1\) ならば \((-2s)^3\neq 1\) なので，\(i\neq j\) ならば \(s_i+2s_j \neq 0\) です．よってこの場合 \(a^i+b^i+c^i=0\) となるのは \(\{a^i, b^i, c^i\} = \{s_1,s_2,s_3\}\) となる場合に限られていて，その確率は \(\frac{6}{27}\) です．

以上で示されました．

【補題】および簡単な考察より，\(1\) 以上 \(p-1\) 以下の整数の組 \((a,b,c)\) を乱択するとき，

  • \(a=b\), \(a=c\), \(b=c\) のいずれかが成り立つ確率：\(O(1/p)\)．
  • \(a+b+c=0\) が成り立つ確率：\(O(1/p)\)
  • \(a^n+b^n+c^n=0\) が成り立つ確率：\(1/4\) 以下
  • \(a^{2n}+b^{2n}+c^{2n}=0\) が成り立つ確率：\(1/4\) 以下
  • \(a^{3n}+b^{3n}+c^{3n}=0\) が成り立つ確率：\(1/4\) 以下

となるので，[2] の乱択アルゴリズムが確率 \(1/4 - O(1/p)\) 以上で成功することが証明できました．

[4] 補足 1

より成功確率の高い乱択解法として，\(a=1, b=-1\) として \(c\) のみを乱択するというものがあります． \(i\) 乗数全体を \(S\) とし \(m=|S|\) とすると，\(-2\notin S\) なら \(a^i+b^i+c^i=0\) となりえず，\(-2\in S\) ならば \(a^i+b^i+c^i=0\) となる確率は \(1/m\) 以下です．定数 \(m\geq 2\) に対して \((-2)^m\equiv 1\pmod{p}\) となる \(p\) は有限個しかないので，この乱択アルゴリズムの成功確率は \(p\to \infty\) のとき \(1\) に収束することが分かります．また，\(a^n,b^n\) の計算が \(O(1)\) 時間で行えるのもこの解法の利点となります．

[5] 補足 2

[3] の証明中の議論から，[2] の乱択アルゴリズムが確率 \(\dfrac{6}{27} + O(1/p)\) で失敗するケースが存在することが分かります．例えば \(p\) を \(p\equiv 1\pmod{3}\) となるようにとり，\(n=\dfrac{p-1}{3}\) とすればよいです．

より詳細な議論をすると，次を示すことができます：

【定理】

[2] の乱択アルゴリズムの失敗確率が \(\dfrac{20}{81} + O(1/p)\) であるような \(p\) が無限に多く存在する．また，\(\varepsilon>0\) に対して，[2] の乱択アルゴリズムの失敗確率が \(\dfrac{20}{81}+\varepsilon\) 以上であるような \(p\) は高々有限個である．

本解説の残りの部分では，このことを証明します．

【注意】以下，本問のレベルを超えた解説となります．また，数学専攻を前提とするレベルの代数学も用いる場面があります．

複素数全体の集合を \(\mathbb{C}\)，素数 \(p\) に対して \(p\) 元体を \(\mathbb{F}_p\) と書くことにします．

【証明の概略】

目標は，\(\mathbb{F}_p\) における \(1\) の \(m\) 乗根 \(\alpha,\beta,\gamma\) であって\((\alpha+\beta+\gamma)(\alpha^2+\beta^2+\gamma^2)(\alpha^3+\beta^3+\gamma^3)=0\) を満たすものの個数を \(p\) に依らない形で評価することです．

例えば NTT （\(\mathbb{F}_p\) における FFT）を学んだ方は，\(\mathbb{F}_p\) における \(1\) の \(m\) 乗根を \(\mathbb{C}\) におけるそれのように扱える場合があることをご存知かと思います．以下の議論でも，\(\mathbb{C}\) における \(1\) の \(m\) 乗根の場合の評価を上手く \(\mathbb{F}_p\) に適用するという手法をとっています．\(\mathbb{C}\) における \(1\) の \(m\) 乗根の間の等式の成立・不成立を \(\mathbb{F}_p\) にうつすために，円分多項式を用います．

【定理の証明】

\(m\) を定数とするとき，次のような記号を準備します．

  • \(\mathbb{C}\) における \(1\) の \(m\) 乗根全体の集合を \(S_0\) とする．これは \(m\) 元集合である．\(S_0\) の要素の \(3\) つ組 \((\alpha, \beta, \gamma)\) は \(m^3\) 通りあるが，そのうち \((\alpha+\beta+\gamma)(\alpha^2+\beta^2+\gamma^2)(\alpha^3+\beta^3+\gamma^3)=0\) を満たすものの個数を \(c_m\) と書くことにする．

  • \(\Phi_m = \prod_{d\mid m}(x^{m/d}-1)^{\mu(d)}\in \mathbb{Z}[x]\) を円分多項式とする．

  • \(0\leq i,j,k < m\) に対して多項式 \(f_{i,j,k}(x)\in \mathbb{Z}[x]\) を \(f_{i,j,k}(x) = (x^i+x^j+x^k)(x^{2i}+x^{2j}+x^{2k})(x^{3i}+x^{3j}+x^{3k})\) で定める．

【補題 A】 \(c_m\) は，\(\Phi_m(x) \mid f_{i,j,k}(x)\) 満たす組 \((i,j,k)\) の個数に等しい．

実際，\(\zeta = \exp(2\pi i/m)\) とすれば，\(\Phi_m\) が \(\zeta\) の \(\mathbb{Q}[x]\) における最小多項式であるという事実と，\(3\) つ組 \((\alpha,\beta,\gamma)\) は一意に \((\zeta^i,\zeta^j,\zeta^k)\) に書けることから証明できます．

次に，\(p\) を \(p\equiv 1\pmod{m}\) を満たす素数とするとき，\(c_{m, p}\) を次のように定めます．

  • \(S_p\) を \(\mathbb{F}_p\) における \(1\) の \(m\) 乗根全体とする．これは \(m\) 元集合である．\(S_p\) の要素の \(3\) つ組 \((\alpha, \beta, \gamma)\) は \(m^3\) 通りあるが，そのうち \((\alpha+\beta+\gamma)(\alpha^2+\beta^2+\gamma^2)(\alpha^3+\beta^3+\gamma^3)=0\) を満たすものの個数を \(c_{m,p}\) と書くことにする．

【補題 B】 上の状況で \(c_m \leq c_{m,p}\) が成り立つ．また，\(c_m < c_{m,p}\) を満たすような \(p\) は高々有限個である．

このことを証明しましょう．\(\zeta\in \mathbb{F}_p\) を \(1\) の原始 \(m\) 乗根のひとつとします．このような \(\zeta\) は存在して \(\Phi_m(\zeta)=0\) を満たすことが，原始根の存在から分かります．

まず，\(\Phi_m(x) \mid f_{i,j,k}(x)\) であるような \((i,j,k)\) に対して \(f_{i,j,k}(\zeta) = 0\) が成り立ちます．よって \((\alpha,\beta,\gamma) = (\zeta^i,\zeta^j,\zeta^k)\) が \((\alpha+\beta+\gamma)(\alpha^2+\beta^2+\gamma^2)(\alpha^3+\beta^3+\gamma^3)=0\) を満たします．したがって 【補題 A】より \(c_m \leq c_{m,p}\) が成り立ちます．

同様の議論から，残りの主張を示すには，次を示せばよいです：

  • \(f \in \mathbb{Z}[x]\) に対して \(\Phi_m(x) \nmid f(x)\) であるとき，\(\Phi_m(\zeta) = f(\zeta) = 0\) を満たす \(\zeta \in \mathbb{F}_p\) が存在するような \(p\) は有限個である．

\(\Phi_m(x)\) は既約多項式であるという事実から，\(\Phi_m(x)\) と \(f(x)\) は互いに素なので，その終結式 \(\mathrm{res}(\Phi_m, f)\) は \(0\) でない整数です．これを \(R \in \mathbb{Z}\) とすると，多項式 \(P(x), Q(x)\in \mathbb{Z}[x]\) が存在して \(R = \Phi_m(x)P(x) + f(x)Q(x)\) が成り立ちます．よって \(\Phi_m(\zeta) = f(\zeta)=0\) ならば \(R=0\) となるので，そのような \(\zeta\) が存在する \(p\) は \(R\) の約数に限られることが分かります．

以上で【補題 B】が示されました．

以上の準備のもと，【定理】の証明に戻ります． 定理は以下の【補題 C】【補題 D】からしたがいます．

【補題 C】 \(p=9n+1\) を十分大きな素数とするとき，\(1\leq a,b,c \leq p-1\) であって \((a^n+b^n+c^n)(a^{2n}+b^{2n}+c^{2n})(a^{3n}+b^{3n}+c^{3n})=0\) を満たすものの個数はちょうど \(\frac{20}{81}(p-1)^3\) である．

\(c_9 = 180\) であることが全探索で分かるので，\(m = 9\) として 【補題 B】を用いると証明できます．

【補題 D】 \(1\leq a,b,c \leq p-1\) であって \((a^n+b^n+c^n)(a^{2n}+b^{2n}+c^{2n})(a^{3n}+b^{3n}+c^{3n})=0\) を満たすものの個数が \(\frac{20}{81}(p-1)^3\) を超えるような \(p\) は高々有限個である．

\(S\) を \(\mathbb{F}_p\) における \(0\) でない \(n\) 乗数全体とし，\(m = |S|\) とします．\(\bigl(\frac{p-1}{m}\bigr)^3c_{m,p} > \frac{20}{81}(p-1)^3\) となる \(p\) が高々有限個であることを示せばよいです．これは \(c_{m,p} > \frac{20m^3}{81}\) と同値です．

\(m\) が十分大きいときには，[3] と同様の議論で \(c_{m,p} \leq 3m^2\) から示すことができます．\(m\) が十分小さいときには高々有限個の例外を除いて \(c_{m,p} = c_{m}\) なので，\(c_m > \frac{20m^3}{81}\) を示せばよく，これは十分小さなすべての \(m\) に対して全探索することで証明できます．

posted:
last update: