約数を格子点として読む

はじめに

※自己紹介は省きます。
約数の個数を求めるとき,素因数分解して指数に$1$足してかけるってのはよく使うと思いますが,そのかけ算を長方形の格子点の個数だと思ってみるとどうでしょう。
たとえば$72=2^3 3^2$の約数は,$2$の指数と$3$の指数で場所を決めて,
$$2^i3^j\longleftrightarrow(i,j),\quad 0\leqq i\leqq3,\quad0\leqq j\leqq2$$
と並べられます。横に$4$点,縦に$3$点なので,全部で$12$点。
この並べ方だと,ある約数の約数を取ることは,左下の長方形を取り出すことになります。積が$72$になる二つの約数は,長方形の中心に関して対称な場所にあります。
こういう見方で,約数の和,最大公約数と最小公倍数,場合の数,整除関係の問題をつなげてみたいってのがこの記事の内容です。前半は入試で使いやすい話,後半は競技数学につながる話にしています。後半も,証明は高校数学で追えるように書いてみます。
序盤は,この並べ方の練習として,約数の公式だけで済む問題もあえて格子点で眺めてみます。少し遠回りだけど,ここで対称な点を組にしたり,左下の部分を取り出したりするのに慣れておくと,後半の話が追いやすくなると思います。
正整数$n$の正の約数の個数を$d(n)$と書きます。また,数え上げの式では,上の数が下の数より小さいコンビネーションを$0$として扱います。

$\text{①}$素因数の指数を座標にする

まず,$1$より大きい正整数$n$の約数を全部並べてみます。相異なる素数$p_{1},\ldots ,p_{r}$を使って,
$$n=\prod_{t=1}^r p_t^{a_t}$$
と素因数分解します。ここでは$a_{1},\ldots ,a_{r}$は正整数です。
$n$の約数はただ一通りに
$$u=\prod_{t=1}^r p_t^{x_t},\quad 0\leqq x_t\leqq a_t\quad(t=1,\ldots,r)$$
と書けます。つまり,約数を選ぶことと各方向の座標を選ぶことが同じになります。各方向で$a_{t}+1$通りずつなので,
$$d(n)=\prod_{t=1}^r(a_t+1)$$
約数の個数の公式が,そのまま直方体の格子点の個数になってます。
ただし,数えているのは体積ではなく格子点です。横の長さが$a$,縦の長さが$b$の長方形なら,境界も含めた格子点は$(a+1)(b+1)$個です。ここは$1$ずれやすいところです。
指数が$0$の方向は一点に縮むと思えばよく,$n=1$も一点に対応します。

約数の条件を座標で言い直す

$u,v$の座標をそれぞれ$x_{t},y_{t}$とすると,次のようになります。

どれも素因数の指数を一つずつ比べれば確かめられます。
たとえば$24$と$18$は,それぞれ$(3,1),(1,2)$にあります。小さい方の座標を取ると$(1,1)$なので最大公約数は$6$,大きい方なら$(3,2)$なので最小公倍数は$72$です。
なお,数として大きいことと,相手を割り切ることは別です。$8$は$9$より小さいですが,$(3,0)$は$(0,2)$の左下にはありません。
約数の和も同じ並べ方で読めます。以下,$\sum$の下の$u$は$n$の正の約数すべてを動くものとすると
$$\sum_u u=\prod_{t=1}^r(1+p_t+\cdots+p_t^{a_t})$$
右辺を展開したとき,格子点に対応する約数が一つずつ出てくるからです。

約数の大小は重みの付いた直線で見る

さっき数としての大小と整除関係は違うって書いたんだけど,じゃあ数としての大小はこの並べ方でどう見えるでしょうか。
相異なる素数$p,q$と非負整数$a,b$について,$n=p^aq^b$とし,約数$u=p^xq^y$を考えます。$u$が$\sqrt n$以下という条件なら,対数を取って
$$x\log p+y\log q\leqq\dfrac{a\log p+b\log q}{2}$$
と書けます。
右辺と等しくなるところが直線なので,長方形の格子点をその直線で区切ってるわけです。$x+y$だけを見るのとは違って,$x,y$にそれぞれ$\log p,\log q$という重みが付いてます。同じだけ指数を増やしても,どっちの素数をかけるかで数の増え方が違うので,その分を重みにしてると思えばいいです。
たとえば$72$の約数$8=2^3$と$9=3^2$なら,座標和は$3$と$2$なのに,$8<9$です。実際の大小を見るときは,$x+y$じゃなく$x\log2+y\log3$を比べることになります。
また,この直線は長方形の中心$\left(\dfrac a2,\dfrac b2\right)$を通ります。積が$n$になる約数の組は,一方が$\sqrt n$より小さければ,もう一方は$\sqrt n$より大きい。これも,中心に関して対称な点が直線の反対側に来ることとして読めます。

$\text{②}$積が$n$になる二つの約数を組にする

$u$と$\dfrac{n}{u}$の座標を足すと,どの方向でも$a_{t}$になります。なので,この二点は直方体の中心に関して対称です。
組の相手が自分自身になるのは,$u^{2}=n$のときだけだから,$d(n)$が奇数になるのは$n$が平方数のときのみ。
また,この組を使うと,すべての約数の積は$n^{\frac{d(n)}2}$になります。約数が奇数個のときも,中央の$\sqrt{n}$だけ残して組にすれば同じ式です。

互いに素になるのは頂点

$u$ $\dfrac{n}{u}$が互いに素となるには,各方向で$\min(x_t,a_t-x_t)=0$となる必要があります。つまり,座標は$0$か$a_{t}$の$2$択です。直方体の頂点を選んでるので,そのような$u$は$2^{r}$個です。
一方,$k$乗数の約数を選ぶなら,各方向で$0,k,2k,\ldots$と座標を選べばよく,個数は
$$\prod_{t=1}^r\left(\left\lfloor\dfrac{a_t}{k}\right\rfloor+1\right)$$

例題$1$：約数の個数を固定して平方を取る

相異なる素数$p,q$と正の整数$a,b$に対して,$n=p^{a}q^{b},d(n)=36$とします。$d(n^{2})$の最大値と最小値を求めてみます。
$(a+1)(b+1)=36$で,$a,b$は正なので,入れ替えを除けば次の四通りです。

最小値は$105$,最大値は$121$です。指数の長方形を,各方向に$2$倍したときの格子点数を比べたことになります。$a,b$に$0$を許すと候補が増えるので,そこは問題文を見ておきたいです。

例題$2$：単位分数の式を約数に直す

正整数$x,y$で,
$$\dfrac1x+\dfrac1y=\dfrac1{12},\quad x\leqq y$$
を満たす組の個数を求めます。
まず$x,y$はともに$12$より大きく,式を整理すると
$$(x-12)(y-12)=144$$
$144$の約数を$u$とすれば,
$$x=12+u,\quad y=12+\dfrac{144}{u}$$
と戻せます。
$144=2^{4}3^{2}$なので約数は$15$個。$u$と$\dfrac{144}{u}$を組にして,真ん中の$u=12$だけ一度数えればいいので,答えは$\dfrac{15+1}{2}=8$

$\text{③}$最大公約数と最小公倍数を指定する

$n$の約数$g,h$があり,$g$が$h$を割り切るとします。
$\gcd(u,v)=g,\operatorname{lcm}(u,v)=h$となる約数の順序つき組$(u,v)$は,$\dfrac{h}{g}$の相異なる素因数が$s$個なら$2^{s}$組あります。
一つの素数について,$g,h$の指数を$b,c$としてみます。$b=c$なら$u,v$の指数はともに$b, b< c$なら,$(b,c)$か$(c,b)$の二通りです。この二択が出る方向の個数が$s$なので,全部で$2^{s}$通りになります。

互いに素な約数の組を数える

$n$の約数から,互いに素な順序つき組$(u,v)$を選びます。一つの方向の指数を$x,y$,上限を$a$とすると,必要なのは$\min(x,y)=0$です。
なので,$(0,0),\ldots ,(0,a)$と,$(1,0),\ldots ,(a,0)$の合計$2a+1$通り。各方向でかけ合わせると,求める個数は
$$\prod_{t=1}^r(2a_t+1)$$
ここで$(u,v)$を$\left(\dfrac{n}{u},\dfrac{n}{v}\right)$に置き換えると,各方向の最小値が$0$という条件は,置き換えた後の最大値が$a_{t}$という条件になるから,$\operatorname{lcm}(u,v)=n$となる順序つき組も同じ個数です。$n=72$なら,どっちも$7\times 5=35$組になります。

$\text{④}$約数の約数を数える

$n$の約数$u$を選び,さらに$u$の約数を選びます。これは$d(u)$を,$n$の全約数について足していることになります。
一つの方向だけ見ると,選ぶ指数は$0\leqq x\leqq y\leqq a$なので,その個数は
$$1+2+\cdots+(a+1)={}_{a+2}\mathrm C_2$$
だから,$u$が$n$の全約数を動くとして,
$$\sum_u d(u)=\prod_{t=1}^r{}_{a_t+2}\mathrm C_2$$
となります。和を実際に全部計算するより,何を選んでいるのかを見た方が楽です。

途中の約数をもっと増やす

重複を許して$k$個の約数を並べ,前の数が次の数を割り切るようにします。一つの方向では,
$$0\leqq x_1\leqq\cdots\leqq x_k\leqq a$$
という指数列を数えることになります。
ここで,指数そのものより,
$$x_1, x_2-x_1,\ldots, x_k-x_{k-1}, a-x_k$$
という隙間を見ます。どれも非負整数で,和は$a$です。逆に,この隙間から元の指数列も戻せます。
非負整数の和を数えるときは,丸と区切りを使えばよく,和が$a$,項が$k+1$個なら${}_{a+k}\mathrm C_k$通りだから,約数列の総数は
$$\prod_{t=1}^r{}_{a_t+k}\mathrm C_k$$
この数え方には,順序つきの因数分解という意味もあります。約数列を$u_{1},\ldots ,u_{k}$とすると,
$$n=u_1\cdot\dfrac{u_2}{u_1}\cdots\dfrac{u_k}{u_{k-1}}\cdot\dfrac n{u_k}$$
と,$k+1$個の正の整数の積に分けられます。逆に,積の先頭から順に掛ければ,約数列に戻ります。

例題$3$：重なった和をそのまま計算しない

$72$の約数$v$ごとに,その約数$u$について$d(u)$を足し,さらに$v$全体について足すといくつになるでしょうか。
これは,三つの約数を並べて,前の数が次の数を割り切るようにする方法を数えています。$72=2^{3}3^{2}$なので,$k=3$として
$${}_6\mathrm C_3\,{}_5\mathrm C_3=20\cdot10=200$$
$d(u)$を一度だけ足すなら
$${}_5\mathrm C_2\,{}_4\mathrm C_2=60$$
和が一段増えた分だけ,選ぶ約数も一つ増えています。

最大公約数の約数を選ぶとどうなるか

今度は,順序つきの約数の組$(u,v)$について$d(\gcd(u,v))$を足してみます。
一つの方向では,指数$x,y$を選んでから,その両方以下の指数$z$を選びます。$z$を先に決めれば,$x,y$はそれぞれ$z$から$a$までなので,$(a-z+1)^{2}$通り。
$$\sum_{z=0}^a(a-z+1)^2=\dfrac{(a+1)(a+2)(2a+3)}6$$
となり,各方向で掛け合わせると
$$\sum_{u,v}d(\gcd(u,v))=\prod_{t=1}^r\dfrac{(a_t+1)(a_t+2)(2a_t+3)}6$$
ここでも$u,v$は$n$の全約数を動きます。

$\text{⑤}$最小値の和を対称な二つの部分に分ける

相異なる素数$p,q$と非負整数$a,b$を取ります。$p^aq^b$の約数$u$を一つ選んで,$u$の約数それぞれについて約数の個数を足してみます。$\text{④}$でやったのと同じ操作です。
積が$p^aq^b$になる相手の約数$\frac{p^aq^b}{u}$についても同じことをして,二つの値のうち小さい方を取ります。これを,$p^aq^b$の全部の約数$u$について足すとどうなるでしょうか。
まず,$u=p^iq^j$なら,$u$について足した値は
$$\sum_{r=0}^i\sum_{t=0}^j d(p^rq^t)=\left(\sum_{r=0}^i(r+1)\right)\left(\sum_{t=0}^j(t+1)\right)={}_{i+2}\mathrm C_2\,{}_{j+2}\mathrm C_2$$
約数の約数を選ぶという操作で,三角数の積が出てきます。
相手の約数は$p^{a-i}q^{b-j}$なので,そっちの値は$i,j$を$a-i,b-j$に替えればいい。格子点では,長方形の点$(i,j)$と,中心に関して対称な点$(a-i,b-j)$を比べているわけです。
なので,今考えている和を$F(a,b)$と書くと,
$$F(a,b)=\sum_{i=0}^a\sum_{j=0}^b\min\left\{{}_{i+2}\mathrm C_2\,{}_{j+2}\mathrm C_2,\ {}_{a-i+2}\mathrm C_2\,{}_{b-j+2}\mathrm C_2\right\}$$
となります。式は長くなったけど,約数$u$それぞれについて,相手の分と比べて小さい方を足してるだけです。
一般の長方形だと,どっちが小さいかを分ける境界は簡単には書けないんだけど,$a=b$なら,境界は$i+j=a$という直線になります。
実は,もう少し一般に,非負整数$n,s$に対して
$$\begin{aligned} &\sum_{i=0}^n\sum_{j=0}^n\min\left\{{}_{i+s}\mathrm C_s\,{}_{j+s}\mathrm C_s,\ {}_{n-i+s}\mathrm C_s\,{}_{n-j+s}\mathrm C_s\right\}={}_{n+2s+2}\mathrm C_{2s+2}+{}_{n+2s+1}\mathrm C_{2s+2} \end{aligned}$$
が成り立ちます。特に$s=2$とすれば,
$$F(n,n)={}_{n+6}\mathrm C_6+{}_{n+5}\mathrm C_6$$

どっちの項を選ぶか

$s$が$1$以上のとき,$1$から$s$までの整数$k$について,
$$(n-i+k)(n-j+k)-(i+k)(j+k)=(n+2k)(n-i-j)$$
$i+j$が$n$以下なら,左辺は非負。したがって,それぞれの積を$k=1,\ldots ,s$について比べると,最小値では第一項を選べます。$i+j$が$n$以上なら第二項です。$s=0$では両項とも$1$なので,同じ分け方でかまいません。
つまり,左下の三角形で第一項を足して$2$倍し,重複して数えた対角線の分を一度引けばいい。

三角形の中の和を数える

コンビネーションの意味使うと,
$$\sum_{i=0}^n\sum_{j=0}^{n-i}{}_{i+s}\mathrm C_s\,{}_{j+s}\mathrm C_s={}_{n+2s+2}\mathrm C_{2s+2}$$
となります。左辺は,$2s+2$個の非負整数の和が$n$以下になる方法を数えています。余りを一つ付け足せば,和がちょうど$n$になる$2s+3$個の非負整数を数える問題になるからです。
対角線上の和は,余りを付け足さずに
$$\sum_{i=0}^n{}_{i+s}\mathrm C_s\,{}_{n-i+s}\mathrm C_s={}_{n+2s+1}\mathrm C_{2s+1}$$
から,求める和は
$$2{}_{n+2s+2}\mathrm C_{2s+2}-{}_{n+2s+1}\mathrm C_{2s+1}={}_{n+2s+2}\mathrm C_{2s+2}+{}_{n+2s+1}\mathrm C_{2s+2}$$
最後はパスカルの関係式を使いました。

$\text{⑥}$因数そのものを座標にすることもある

ここで少しだけ,座標の取り方を変える話も挟んでおきます。ここまでは,一つの整数を固定して,その約数を素因数の指数で並べてきました。
いろいろな整数について約数の個数をまとめて足すときは,かけてその整数になる二つの因数を,そのまま座標にする方が数えやすいこともあります。何を数えたいかで座標の選び方も変わる,という補足です。
正の整数$X$に対して,
$$\sum_{m=1}^X d(m)$$
は,$xy$が$X$以下となる正整数の組$(x,y)$の個数です。$xy=m$となる組が,$m$ごとに$d(m)$個あるからです。
$$h=\lfloor\sqrt X\rfloor$$
と置くと,どの点も$x$が$h$以下か,$y$が$h$以下のどっちかを満たします。両方とも$h$より大きいと,積が$X$を超えてしまうからです。
$x,y$がともに$h$以下の正方形には$h^{2}$点あり,この部分を二重に数えないようにすると,
$$\sum_{m=1}^X d(m)=2\sum_{x=1}^h\left\lfloor\dfrac Xx\right\rfloor-h^2$$
となります。$X=10$なら,$2(10+5+3)-9=27$です。
固定した整数の約数なら指数の直方体,積に上限がある総和なら双曲線の下の格子点。何を座標にしているかで使いやすい場面が変わります。

$\text{⑦}$素因数の個数をそろえると断面になる

$u$の素因数の個数を,重複も含めて$\Omega(u)$と書きます。$\Omega(1)=0$とし,たとえば$\Omega(72)=5$です。
$u$の座標が$x_{1},\ldots ,x_{r}$なら,
$$\Omega(u)=x_1+\cdots+x_r$$
なので,$\Omega(u)=k$となる約数を数えることは,座標和が$k$の断面にある格子点を数えることになります。
その個数を$T(k)$,指数の上限の和を$A=a_{1}+\cdots +a_{r}$と書くと,
$$\prod_{t=1}^r(1+z+\cdots+z^{a_t})=\sum_{k=0}^A T(k)z^k$$
各因子から$z$の累乗を一つずつ選ぶことが,約数の座標を一つずつ選ぶことに対応してます。
また,$u$と$\dfrac{n}{u}$を組にすると座標和が$k$と$A-k$になるので,
$$T(k)=T(A-k)$$

三方向なら包除原理で数えられる

$n=p^{a}q^{b}r^{c}$とします。$p,q,r$は相異なる素数で,$a,b,c$は非負整数です。
上限のない$x+y+z=k$の非負整数解は,丸と区切りで数えると${}_{k+2}\mathrm C_2$個で,こっから$x$が$a+1$以上のものを除きます。そのような解は,$x$から$a+1$を引けばいいので,個数は${}_{k-a+1}\mathrm C_2$
他の二方向も同じように引き,二つの上限を超えたものを戻し,三つとも超えたものをもう一度引くと,
$$\begin{aligned} T(k)={}&{}_{k+2}\mathrm C_2-{}_{k-a+1}\mathrm C_2-{}_{k-b+1}\mathrm C_2-{}_{k-c+1}\mathrm C_2+{}_{k-a-b}\mathrm C_2+{}_{k-a-c}\mathrm C_2+{}_{k-b-c}\mathrm C_2-{}_{k-a-b-c-1}\mathrm C_2 \end{aligned}$$
上の数が$2$より小さい項を$0$とする約束で,解がない場合も一緒に書いてます。

例題$4$：$60$個の約数を断面に分ける

$n=2^{4}3^{3}5^{2}$とすると,$k=0,\ldots ,9$に対する$T(k)$は順に
$$1,\ 3,\ 6,\ 9,\ 11,\ 11,\ 9,\ 6,\ 3,\ 1$$
たとえば$k=4$なら,上限のない解$15$個から,$y$が$4$以上の$1$個と,$z$が$3$以上の$3$個を引いて,
$$T(4)={}_6\mathrm C_2-{}_2\mathrm C_2-{}_3\mathrm C_2=11$$
です。残りも同じ公式で数えられ,後半は対称性から出せます。全部足すと,ちゃんと$60=(4+1)(3+1)(2+1)$になります。

中央の断面だけなら両隅を切り取ればいい

ここからは
$$0\leqq a\leqq b\leqq c,\quad a+b+c=2m$$
とします。$\Omega(u)=\Omega\left(\dfrac{n}{u}\right)$となる約数の個数を$C$とすると,求めるのは$x+y+z=m$となる点です。
$z=m-x-y$と決まるので,$x,y$の長方形だけ見れば十分です。
$\text{①}c$が$a+b$以上なら,$a+b$が$m$以下,$m$が$c$以下です。そのため,長方形のどの$(x,y)$にも条件を満たす$z$が一つ対応して,
$$C=(a+1)(b+1)$$
$\text{②}c$が$a+b$より小さいときは,$h=\dfrac{a+b-c}{2}$と置くと,必要な条件は
$$h\leqq x+y\leqq a+b-h$$
左下の$x+y< h$の部分と,その対称な右上の部分を除けばいい。
$c$が$b$以上なので$a$は$2h$以上です。したがって,除く二つの三角形が長方形の端で欠けることはありません。それぞれの点数が$1+2+\cdots +h$なので,
$$C=(a+1)(b+1)-h(h+1)$$
なお,ここでそろえているのは素因数の個数です。約数が$\sqrt{n}$以下かどうかとは違います。$n=36$なら,$4$と$9$はどちらも$\Omega=2$の中央断面にありますが,$6$より小さいものと大きいものに分かれてます。

$\text{⑧}$偶奇や余りで分けて数える

$\text{⑦}$の多項式に$z=-1$を入れてみます。$\Omega(u)$が偶数なら +$1$,奇数なら −$1$が付くので,偶数側の個数から奇数側の個数を引いた値が出ます。
各方向では,
$$1-1+\cdots+(-1)^{a_t}=\begin{cases}1&(a_t\text{ が偶数})\\0&(a_t\text{ が奇数})\end{cases}$$
だから,個数の差は$n$が平方数なら$1$,それ以外なら$0$になります。
同じ考え方は,約数を$3$で割った余りにも使えます。

例題$5$：$2026$年東大理系第$6$問とのつながり

$n$の正の約数のうち,$3$で割って$1$余るものの個数を$f(n),2$余るものの個数を$g(n)$とすると,
$$f(n)\geqq g(n)$$
が成り立ちます。
これは,$2026$年東京大学・理系数学第$6$問の$(2)$と同じ内容です。下で使う$2800$の具体例も,同じ問題の$(1)$です。 2026年東京大学理系数学 の第$6$問を見てみてください。
同じ問題を格子点で眺める話として,田畑賢大さんの 「今年の東大理系第$6$問(整数)を目で解く」 も紹介しておきます。素因数の指数を座標にして,偶奇による打ち消しを図で見られる記事です。そっちも読むと,このあと出てくる符号の話が見えやすくなると思います。
まず,$3$で割り切れる約数はどっちにも数えません。素因数$3$の方向は,指数を$0$に固定しておけばいいです。
$3$で割って$1$余る素数なら,何乗しても$1$余ります。その方向の指数の上限が$a$なら,個数の差には$a+1$が掛かります。
$3$で割って$2$余る素数なら,指数の偶奇で余りが$1,2$と交互に変わります。余り$1$に +$1$,余り$2$に −$1$を付けると,その方向の和は
$$1-1+\cdots+(-1)^a$$
これは$a$が偶数なら$1$,奇数なら$0$になります。
余りのかけ算に合わせて符号も掛け合わされるので,$f(n)-g(n)$は,この各方向の和をかけたものです。どの因子も非負なので,$f(n)$が$g(n)$以上だと分かります。
たとえば$2800=2^{4}5^{2}7$なら,$2$と$5$の方向では$1,7$の方向では$2$が残ります。よって,
$$f(2800)+g(2800)=30,\quad f(2800)-g(2800)=2$$
から,$f(2800)=16,g(2800)=14$です。
指数の長方形で見るなら,$2$と$5$の方向では隣り合う二つの場所の符号が打ち消し合って,最後に一つだけ残ってます。式の積を覚えるより,こっちの方が自分には見やすいです。
東大の$(3)$は,$g(n)=15$のときに$f(n)$が取りうる値を求める問題です。上で見たどこかの方向で全部打ち消し合う場合と各方向で一つずつ残る場合を分けるところから続きも考えられます。

$\text{⑨}$互いに割り切れない約数をできるだけ多く選ぶ

$n$の約数をいくつか選び,異なる二つのどっちも他方を割り切らないようにします。このような集まりは反鎖と呼ばれてます。
座標和が同じ点だけ選べば,必ずこの条件を満たします。一方が他方の各座標以下で,どっか一つでも小さければ,座標和も小さくなってしまうからです。
では,別の断面の点を混ぜるともっと多く選べるでしょうか。

平方因子を持たない場合

まず$n$が,相異なる$r$個の素数の積だとします。
素数を一列に並べ,$1$から始めて,先頭の素数から順にかけていきます。すると,前の数が次の数を割り切る約数列ができます。このような列を鎖と呼びます。
選んだ反鎖の約数は,一本の鎖に高々一つしか入りません。一方,素因数を$j$個持つ特定の約数が,この鎖に現れる並べ方は$j!(r-j)!$通りです。
並べ方全体は$r!$通りなので,選んだ約数を$u$として数えると,
$$\sum_u j!(r-j)!\leqq r!,\quad j=\Omega(u)$$
つまり,
$$\sum_u\dfrac1{{}_r\mathrm C_{\Omega(u)}}\leqq1$$
ここで$u$は,選んだ約数すべてを動きます。
コンビネーションが最大になるのは中央なので,選べる個数は中央のコンビネーション以下です。実際,中央の断面を全部選べば,その個数を達成できます。これは$\text{Sperner}$の定理や$\text{LYM}$不等式につながる話です。

指数が$2$以上になるときの注意

$n=p^{2}q$で,$p,p,q$を並べてみます。異なる並べ方は三通りですが,先頭が$p$なのは二通り,$q$なのは一通りです。同じ断面にあっても,鎖に現れる回数が違ってしまいます。
なので,そのまま同じ数え方をするのは危ない。一般の場合は,全体を鎖に分ける方法を考えます。

$\text{⑩}$直方体全体を鎖に分ける

各座標の上限の和を,引き続き$A$とします。
一度に一つの座標だけを$1$増やして進む鎖で,始点と終点の座標和を足すと$A$なるものを,対称鎖と呼びます。
たとえば,座標和が$2$の点から始まって$A-2$の点で終わる鎖です。途中の座標和は一つずつ増えるので,どの対称鎖も中央の断面を一度ずつ通ります。

まず長方形で考える

$$0\leqq x\leqq L,\quad0\leqq y\leqq b$$
の長方形で,$j=0,\ldots ,\min(L,b)$に対して,
$$(0,j),(1,j),\ldots,(L-j,j),(L-j,j+1),\ldots,(L-j,b)$$
という鎖を取ります。曲がる点は一度だけ数えます。
下の横一列と右の縦一列を取って,その残りでも同じことを繰り返す,と思えば分かりやすいです。
たとえば$L=4,b=3$なら,最初は$y=0$を右に進んでから$x=4$を上に進み,次は$y=1$を右に進んでから$x=3$を上に進みます。こうして,$8$点,$6$点,$4$点,$2$点の四本に分かれます。
重複や抜けがないことも確認しておきます。点$(x,y)$が入る鎖の番号は$\min(y,L-x)$なので,一意に決まります。
また,$j$番目の鎖の始点と終点の座標和は$j$と$L+b-j$。足すと$L+b$なので,どれも対称鎖です。

方向を一つ増やす

ある直方体が対称鎖に分かれているとします。一本の鎖の始点の座標和を$s$,そこから終点までの歩数を$L$とすれば,
$$L=A-2s$$
ここに,指数が$0$から$b$までの方向を一つ加えます。元の鎖の上で何歩進んだかと,新しい座標を組にすれば,$L$と$b$を上限とする長方形になります。これを,さっきの方法で分ければいい。
元の始点の座標和$s$も含めると,新しい鎖の両端の座標和の合計は,
$$2s+L+b=A+b$$
なので,方向を増やした後も対称鎖に分かれます。一方向では全体が一本の鎖なので,帰納法でどの直方体でもできます。

これで最大個数が分かる

反鎖からは,一本の鎖につき高々一つしか選べません。すべての対称鎖が中央を一度ずつ通るので,鎖の本数は中央断面の点数と同じです。
中央断面を全部選べば実際に達成できるので,求める最大個数は
$$T\!\left(\left\lfloor\dfrac A2\right\rfloor\right)$$
また,中央より下の点は,同じ鎖の次の点へ重複なく移せます。このため$T(k)$は中央に向かって減らず,中央から先は対称性によって増えません。

例題$6$：$60$個の約数から最大何個選べるか

$n=2^{4}3^{3}5^{2}$の約数から,互いに割り切れないものを選ぶとします。
$\text{⑦}$で中央の断面は$11$点だったので,最大は$11$個です。$\Omega(u)=4$の約数を全部取れば達成できます。
同じ断面から取れることだけでは,最大だとまでは言えません。全体を鎖に分けたことで,これ以上は取れないも言えたわけです。

三つ以上の整除列を禁止するなら

異なる$k+1$個の約数が,前の数が次の数を割り切る順に並ばないように選ぶとします。ここでは
$$1\leqq k\leqq A+1$$
一本の鎖に選べるのは$k$個までで,鎖が$k$点より短ければ全点までです。この上界は,中央に最も近い連続した$k$個の段を,丸ごと選ぶことで同時に達成できます。
どの対称鎖も中央に関して対称な連続区間を通るので,長さが$k$以上なら選ぶ部分に$k$点,$k$未満なら全点が入るからです。また,選んだ点の座標和は$k$種類しかないので,異なる$k+1$点の整除列はできません。
したがって最大個数は,$T(0),\ldots ,T(A)$の大きい方から$k$個を足したものです。上の$60$個の約数で,三つの整除列を禁止するなら,最大は$11+11=22$個になります。

$\text{⑪}$二方向ずつの情報から,全体を抑える

$n=p^{a}q^{b}r^{c}$の約数をいくつか選んで,その個数を$N$とします。
選んだ各約数から$r$の因子を全部取り除いたとき,異なる数が$P$個現れたとします。同じように,$q$の因子を取り除いたときは$Q$個,$p$の因子を取り除いたときは$R$個とします。
座標で言えば,$xy,xz,yz$平面に投影したときの点数です。このとき,
$$N^2\leqq PQR$$
が成り立ちます。
さらに,空でない場合に等号になるのは,各方向で使う座標を決めて,その組合せを全部選んでいるときです。使う座標は連続していなくてもかまいません。

コーシーシュワルツを二回使う

各投影に点があれば$1$,なければ$0$となる数を,$xy$投影で$f(x,y),xz$投影で$g(x,z),yz$投影で$h(y,z)$とします。
以下の$x,y,z$の和は,それぞれ$0$から$a,0$から$b,0$から$c$までです。
選んだ点なら三つの投影に必ず現れるので,
$$N\leqq\sum_{x,y}f(x,y)\sum_z g(x,z)h(y,z)$$
です。まず$z$についてコーシーシュワルツを使います。$g,h$は$0$か$1$なので,その二乗は元と同じです。したがって,
$$N\leqq\sum_{x,y}f(x,y)\sqrt{\left(\sum_zg(x,z)\right)\left(\sum_zh(y,z)\right)}$$
となります。さらに$x,y$についてもう一度使うと,
$$\begin{aligned} N^2 &\leqq P\sum_{x,y}f(x,y)\left(\sum_zg(x,z)\right)\left(\sum_zh(y,z)\right)\\ &\leqq P\sum_{x,y}\left(\sum_zg(x,z)\right)\left(\sum_zh(y,z)\right)\\ &=P\left(\sum_{x,z}g(x,z)\right)\left(\sum_{y,z}h(y,z)\right)\\ &=PQR \end{aligned}$$
等号条件も見ておきます。最後に$f$を外したところが等号なら,実際に現れる$x$と$y$の組は,すべて$xy$投影に現れます。
また,最初に使ったコーシーシュワルツが等号なら,各$x$に対応する$z$の候補と,各$y$に対応する$z$の候補が一致します。どっちも空でない$0,1$の列なので,比例するには同じ列になる必要があるからです。
さらに最初の$N$の評価も等号なら,三つの投影と整合する点は全部選ばれています。これで,各方向の候補を独立に組み合わせた全配置だと分かります。
逆に,各方向の候補が$u,v,w$個なら,$N=uvw,P=uv,Q=uw,R=vw$なので,確かに等号です。
これは$\text{Loomis–Whitney}$の投影不等式の三次元・離散版です。この見方に関連して, 私（$\text{@etheron126}$）の投稿 も置いておきます。
また,不等式そのものは $\text{IMO}1992$年第$5$問 に出てます。 公式 では,空間内の有限個の点と,三つの座標平面への投影について問われてます。約数に限った話を,空間の点の配置まで広げた形です。

例題$7$：投影の個数が$12,15,20$のとき

$P=12,Q=15,R=20$なら,$N$は$60$以下です。
等号の場合,各方向の候補の個数は
$$\sqrt{\dfrac{PQ}{R}}=3,\quad\sqrt{\dfrac{PR}{Q}}=4,\quad\sqrt{\dfrac{QR}{P}}=5$$
になります。実際,$x$を$0$から$2,y$を$0$から$3,z$を$0$から$4$まで独立に選べば,$60$点で達成できます。約数では$2^{2}3^{3}5^{4}$の全約数が一例です。
ここに選んだ数の約数は,全部選ばれてるという条件も加えてみます。
等号配置では,各方向の候補が$0$から始まる連続した整数になります。飛び飛びに選ぶと,その下にある約数が抜けてしまうからです。したがって,この場合の等号配置は,ある一つの整数の全約数になります。

$\text{⑫}$中央断面と全体の個数を結び付ける

最後に,ここまでの見方を使う例を一つ。

例題$8$

$a,b,c$を非負整数として,
$$a+b+c=2026,\quad n=2^a3^b5^c$$
とします。$\Omega(u)=\Omega\left(\dfrac{n}{u}\right)$となる$n$の約数$u$の個数を$C$とします。
$$C^2=d(n)$$
が成り立つとき,$n$の最大値を求めます。
まず指数を小さい順に並べ,その値を改めて$a,b,c$と書きます。$C$と$d(n)$は,方向を入れ替えても変わりません。どの素数にどの指数を付けるかは,最後に考えます。
$\text{①}c$が$a+b$より小さい場合
$h=\dfrac{a+b-c}{2}$と置きます。指数の和が偶数なので$h$は正の整数で,$a,b$はともに$2h$以上です。$\text{⑦}$より,
$$C=(a+1)(b+1)-h(h+1)$$
$c=a+b-2h$を使って計算すると,
$$\begin{aligned} C^2-(a+1)(b+1)(c+1) ={}&(a+1)(b+1)(ab-2h^2)+h^2(h+1)^2>0 \end{aligned}$$
$ab$が$4h^{2}$以上で,$h$が正だからです。したがって,この場合は$C^{2}=d(n)$になりません。
$\text{②}c$が$a+b$以上の場合
今度は$C=(a+1)(b+1)$なので,$C^{2}=d(n)$を整理すると,
$$c+1=(a+1)(b+1)$$
指数の和と合わせれば,
$$ab+2a+2b=2026,\quad(a+2)(b+2)=2030$$
$2030=2\cdot 5\cdot 7\cdot 29$なので,$a$が$b$以下となる因数の組を調べると,次の七通りです。

どの行でも$c-a-b=ab$なので,今考えている条件も満たします。
$\text{③}$どの行で最大になるか
大きい素数に大きい指数を付けた方が,整数は大きくなります。二つの指数を入れ替えたときの比を取れば,すぐに確かめられます。なので,各行では小さい順の指数を$2,3,5$に付ければいい。
表の次の行に移るたび,$b$の減少量は$a$の増加量の$2$倍以上になってます。
$a$を$1$増やし,$b$を$2$減らし,$c$を$1$増やすと,整数は
$$\dfrac{2\cdot5}{3^2}=\dfrac{10}{9}>1$$
倍になります。残りの$b$の減少分を$c$に回す操作でも,そのたびに$\dfrac{5}{3}$倍になります。したがって,次の行へ進むほど大きくなります。
よって,最大値は最後の行の$2^{33}3^{56}5^{1937}$
実際,$C=34\cdot 57=1938$で,$c+1$も$1938$なので,$d(n)=1938^{2}$となって条件を満たします。
この問題では,中央断面が長方形全体になる場合と,両隅を切り取る場合に分けたところが効いています。大きな指数を直接追う前に,どんな形の断面になっているかを見ると進めやすいです。

関連する入試・競技数学・自作問題

読み終わったあとに取り組むなら,このあたりもつながるかなぁ。出典と,この記事のどこを使えそうかを一緒に置いときます。

ブリザードマンさんは $\text{note}$ にもめちゃくちゃ質のいい入試解説や自作模試を公開されています。上の投稿については,ここでは確認できた条件と,その条件がこの記事とどうつながるかを紹介しています。

おわりに

約数を一つずつ書き出していると,和や条件が増えたところで大変になりがちです。でも,指数を座標にすると,左下を取る,中心に関して反転する,同じ座標和で切るといった形に直せることがあります。
毎回この見方を使う必要はないと思うけど,約数の条件がいくつも重なってきたときに,一度こう並べてみると,式だけ見ていたときより分かりやすくなることがあります。

読んでいただきありがとうございました。自分が知らないだけで内容が被っている文献はあるかもです🙇‍♂️

参考文献

• 東京大学： $2026$年度数学（理科）の問題
• $\text{International Mathematical Olympiad}$： $1992$年の問題 , $2002$年の問題