(69)京大オープンで約数の個数絡みの整数問題は不等式評価で解けることを確認する世界線

こんばんは。今日は京大オープンのこれをやります。

とりあえずnの約数の個数はn＝p_1^a_1p_2^a_2…+p_k^a_kみたいになったら

f(n)＝(1+a_1)…(1+a_k)

みたいになります。

このとき、普通にp_1^a_1と1+a_1を比較したら指数的増大をするから明らかにp_1^a_1が大きくなりそうなお気持ちがあります。そういう気持ちを大事にしたら

5^n>2(1+n)

2^n≧(1+n)

みたいな不等式が得られて、これから今回の問題のnは2と3しか素因数を持たないことがわかります。この後もこういう不等式のお気持ちを大事にするとNが特定できます。

約数の和の問題は特にこういう不等式のお気持ちが強くなるので、そういうことを意識してやると良いでしょう。