N以下のNの約数ではないN^2の約数の個数を求めよう
$N$以下の$N$の約数ではない$N^2$の約数の個数を求めよ.
たとえば$N=12$とすると$8$,$9$のふたつが満たす。
約数は正のものをいうことにし、$|X|$で集合$X$の要素数を表す
$\\[5cm]$
↓解答
$\\[15cm]$
$N=p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$とする.
さて, $$S=\{p_1^{f_1}p_2^{f_2} \cdots p_m^{f_m} \mid (0 \leq f_i \leq 2e_i (0 \leq i \leq m)) \land
(あるi,jが存在しf_i>e_i, f_j< e_j) \}$$とすると答えは$\frac{|S|}{2}$である.
$S \ni d$と$\frac{N^2}{d}$について考える.
$d=p_1^{f_1}p_2^{f_2}\cdots p_m^{f_m}$とし, $f_i>e_i$, $f_j< e_j$であるとする.
すると$$\frac{N^2}{d}=p_1^{2e_1-f_1}p_2^{2e_2-f_2}\cdots p_m^{2e_m-f_m}$$であり$2e_i-f_i< e_i$, $2e_j-f_j>e_j$だから$\frac{N^2}{d} \in S$である.
また, $\min(d,\frac{N^2}{d})\le N$となり, $f_i>e_i$および$2e_j-f_j>e_j$より, $d$, $\frac{N^2}{d}$のうちちょうど$1$つは$N$以下の$N$の約数ではない$N^2$の約数である.
よって, $\fbox{Answer}\geq \frac{|S|}{2}$.
逆に $N^2$の約数で$S$に属さないものは,
(1) $f_i>e_i$となる$i$が存在しないとき:$N$の約数になり不適
(2) $f_i< e_i$となる$i$が存在しないとき:$N$より大きくなり不適
よって, $\fbox{Answer} \leq \frac{|S|}{2}$であり先ほどの結果とあわせて $\fbox{Answer} = \frac{|S|}{2}$であることが示された.
$f_i>e_i$もしくは$f_i< e_i$を満たす$i$の集合を決め打って$|S|$を計算していく方針で,
\begin{align*}
\fbox{Answer} &= \frac{|S|}{2}\\
&=\frac{1}{2}\left[\sum_{\substack{I \subset \{1,2,\cdots ,m\}\\|I|\geq2}}
\left(\left(\prod_{i \in I} 2e_i\right) - 2\left(\prod_{i \in I} e_i\right)\right)\right]\\
&= \frac{1}{2}\left[\left(\prod_{i=1}^m (1+2e_i)\right)-2\left(\prod_{i=1}^m (1+e_i)\right)+1\right]
\end{align*}
(最後の$+1$の部分で$|I|=0$,$1$のケースを除外した)
おつかれさまです。$\LaTeX$のコードをはっつけてみたら書式がちょっと違くて修正がたいへん...
