今回扱うのはyukicoder contest 368 B問題 No.2125 Inverse Sumです。公式解説が非常に分かりやすくまとまっているので問題の解法そのものはそちらをご覧ください。

この記事の目的は、公式解説を読んで「どうやったらこの解法が思いつくのだろう？」と思った人向けに想定解までの道のりを紹介することです。

問題の概要

正確な問題文はこちらです。

$2$個の正整数$P, Q$が与えられます。方程式

\[ \frac{1}{n} + \frac{1}{m} = \frac{P}{Q} \]

を満たす正整数の組 $(n,m)$ を全て求めてください。

極めてシンプルで、それでいて慣れていないと全然取っ掛かりが見つからない、面白い問題です。

どのように考察するとよいでしょうか？

ステップ1: 式の整理

何はともあれ、この問題に限らず数学の問題は同値変形で分かりやすくすることを検討しましょう。

分数を含む方程式は、分母を払って整数のみの方程式として処理するのが典型です。

というわけで両辺に$Qnm$を掛けて分母を払って移行した式は

\[ Pnm - Qn - Qm = 0 \]

です。まだ解き方が分かりませんね。

ステップ2: 方程式の分類

実数の方程式では、変数が $2$ 個で式が $1$ 個だと解が無限個存在しそうで不安になる人も多いと思います。（実際には$x^2+y^2=-1$のように解が$0$個のものや$x^2+y^2=0$のように解が$1$個のものもありますが）

一方で整数のみの方程式（特にディオファントス方程式）では、$2$つの数値の間に無限個の実数があるにも関わらず整数は有限個しかないという特殊事情から、変数の個数より式の本数が少なくても解が有限個しかない状況が多発します。

もちろん整数の方程式でも解が無限個になることはあり、例えば$1$次方程式でいくらでも例が作れますが、そういう問題では解を全て挙げさせることが当然できません。例えば解の範囲を制限してその中に入るものだけを挙げさせたり、適当な法で割った余りを挙げさせるなど、無限個あるうちの一部だけを挙げさせるように問題文が工面されるでしょう。

一方で今回は範囲の制限も法での剰余もなく解を全て挙げることが要求されているので、そもそも解が有限個であることが保証されているわけです。これはある意味ヒントとなります。

$2$変数$n,m$の整数係数$2$次方程式には色々な種類がありますが、実数の範囲に拡張して考えれば$2$次曲線の分類から次の$3$パターンとなります：

1. 実数の方程式としては解が楕円を描くパターン。
2. 実数の方程式としては解が放物線を描くパターン。
3. 実数の方程式としては解が双曲線を描くパターン。

今回も整数係数$2$次方程式ですが、どれに該当するでしょう？

1は実数解が有界（絶対値の上限が有限）なので、整数解は有限個です。有界な範囲に実数は無限個ありえますが、整数は有限個しかないからですね。このパターンは、その有界な範囲で全探索をしたり、片方の変数を固定して平方根を整数の範囲で求めるなどの方法で解くことができます。

1の方程式は$n^2$と$m^2$の係数が正となります。今回は$n^2$と$m^2$の係数が$0$なので違いますね。

2は実数解が非有界です。それどころか、実は整数解が無限個になることもありますし、$0$個になることもあります。無限個になるパターンは$n^2+3m+2 = 0$を、$0$個になるパターンは$n^2+4m+1 = 0$を思い浮かべていただければ分かりやすいです。

2の方程式は$n^2$か$m^2$の少なくとも一方の係数が正になります。やはり今回は$n^2$と$m^2$の係数が$0$なので違いますね。

というわけで、今回は3のパターンであると判断できました。実際、実数の方程式として$Pnm - Qn - Qm = 0$の解をプロットしてみれば双曲線がお目にかかれます。

ステップ3: 双曲線の格子点の決定

以上で双曲線の格子点を求める問題であることまでは分かったのですが、双曲線の格子点の決定問題は以下の$2$つに分類できます。

1. ペル方程式型（整数の範囲では因数分解できない斉次$2$次式と定数の差が$0$）
2. 反比例型（整数の範囲では因数分解できる斉次$2$次式と定数の差が$0$）

1は$n^2 - 61m^2 - 1 = 0$が典型例です。斉次$2$次式部分$n^2 - 61m^2$が整数の範囲で因数分解できないのでどうせ$(n,m) = (1,0)$以外に解がなさそうかと思いきや、$(n,m) = (1766319049,226153980)$とかいう解が出てきて初学者をびっくりさせます。

ペル方程式は連分数展開やチャクラバーラ法で解くことができますが、ペル方程式は★2.5で問われないこと、実は整数解が無限個あることから、今回は気にしなくて良いことが分かります。

ワヘイヘイの日常第2章39～40ページより抜粋

なおここでは便宜上ペル方程式型と勝手に呼びましたが、ペル方程式でないものもあります。例えば$x^2 - 10y^2 - 12 = 0$などです。こういったペル方程式の拡張は一般には難しいので、やはり★2.5では問われません。今回は気にしないことにしましょう。

というわけで狙いを定めるべきは2で、$nm - 6 = 0$や$(n+m)(n-4m) - 18 = 0$のように整数の範囲でも因数分解できる斉次$2$次式と定数の差が左辺に現れるパターンになることを期待しましょう。これなら定数部分の約数列挙で解くことが可能です。

そうと分かれば、与えられた方程式$Pnm - Qn -Qm = 0$を同値変形することで何らかの整数値$2$変数関数$f,g$と整数定数$c$を用いた方程式$f(n,m) g(n,m) + c = 0$に持ち込めないか考えましょう。同値変形前の式が$2$次式であることから、まずは$f,g$ともに$1$次式である場合を検討するのが自然ですね。

ステップ4: 係数決定

ここまで来ればもう$f,g$は大体勘で探して見付かるものですが、万が一運悪く見付からなったとします。

そういう時は仕方ないので、定数$a_1,a_2,a_3,b_1,b_2,b_3$を用いて

\[ \begin{align} f(n,m) =& \ \ a_1 n + a_2 m + a_3 \\
g(n,m) =& \ \ b_1 n + b_2 m + b_3 \end{align} \]

と置いて定数を求めてみます。

\[ \begin{align} & \ \ f(n,m) g(n,m) + c \\
= & \ \ a_1 b_1 n^2 + a_2 b_2 m^2 + (a_1 b_2 + a_2 b_1) nm + (a_3 b_1 + a_1 b_3) n + (a_3 b_2 + a_2 b_3) m + a_3 b_3 + c \end{align} \]

となりますが、元の方程式の$n^2$と$m^2$の係数が$0$だったことから、同値変形後に現れる$n^2$と$m^2$の係数も$0$になってくれることを期待して、$a_1 b_1 = a_2 b_2 = 0$となる場合を最初に検討するのが自然です。

$a_1 b_1 = 0$より$a_1 = 0$または$b_1 = 0$が成り立ちますが、必要ならば$f,g$を$g,f$に入れ替えても良いので、例えば$a_1 = 0$としましょう。$a_2 = 0$ならば$f(n,m) = a_3$となり、これは$1$次式でないので$a_2 \neq 0$とします。すると$a_2 b_2 = 0$から$b_2 = 0$が従います。

\[ f(n,m) g(n,m) + c = a_2 b_1 nm + a_3 b_1 n + a_2 b_3 m + a_3 b_3 + c \]

となり、だいぶ元の方程式に近づいてきました。元の方程式は$(n,m) = (0,0)$を解に持つ（問題の答えでは正の解しか列挙しませんが考察において同値変形などを考える際は$(n,m)$を実数の組としても$(0,0)$としても良いです）ことから$f(n,m) g(n,m) + c = 0$が元の方程式と同値になるためには$(n,m) = (0,0)$を解に持つ必要があり、これにより$a_3 b_3 + c = 0$となるので

\[ f(n,m) g(n,m) + c = a_2 b_1 nm + a_3 b_1 n + a_2 b_3 m \]

となります。元の方程式$Pnm - Qn - Qm = 0$と$a_2 b_1 nm + a_3 b_1 n + a_2 b_3 m = 0$が同値になるには後者が前者の非零定数倍になればよく、例えば$(a_2,a_3,b_2,b_3) = (P,Q,P,Q)$とすれば十分です。

得られた方程式は

\[ (Pn+Q)(Pm+Q) - Q^2 = 0 \]

です。これが解説で紹介された式ですね。