12110008

説明

• 約数の個数の公式～任意の自然数kで定まるa_kは互いに異なる素数を表しb_kを自然数とする。 　 　　　この時、自然数Π[k=1,m](a_k)^(b_k)の約数の個数は

  (b_m+1)*(b_(m-1)+1)*…*(b_1+1)個
  (=Π[k=1,m](b_k+1)個)
  

  • なぜこうなるかというと、例えばN=2^3*3^2の時の約数は2^m*3^nで表されます。

　　　　　　　　　ここで、mの選び方は0～3,nの選び方は0～2通り。

　　　　　　　　　この組み合わせを掛け合せて(3+1)(2+1)=12通りです。

　　　　　　　　　このようにしてそれぞれの素数についてのm乗の選び方

　　　　　　　　　の組み合わせを求めます。

• 約数の総和の公式～任意の自然数kで定まるa_kは互いに異なる素数を表しb_kを自然数とする。

　 この時、自然数Π[k=1,m](a_k)^(b_k)の約数の個数は

((a_m)^(b_m+1)-1)/(a_m-1) * ((a_(m-1))^(b_(m-1)+1)-1)/(a_(m-1)-1)…* ((a_1)^(b_1+1)-1)/(a_1-1)個
(=Π[k=1,m]((a_k)^(b_k+1)-1)/(a_k-1)個)

• これの理由も上と似ています。kの値で分けて考えます。a_1のみの約数について

　　　　　　　　　a_1^0からa_1^(b_1)までが考えられるから

　　　　　　　　　((a_1)^(b_1)+(a_1)^(b_1-1)+…+(a_1)^0)

　　　　　　　　　これにa_k-1を分母分子にかけて((a_1)^(b_1+1)-1)/((a_1)-1)。

　　　　　　　　　これはほかのa_kについても同様に成り立つからこれらをかけあわせて上の公式を導く。

NO.8-1　約数の総和

問題

 53 ：以下、名無しにかわりましてVIPがお送りします：2008/11/29(土) 18:54:53.60 ID:XJP+DC730
   制限時間11分　難易度３（実戦基礎）
   960の約数の総数は{アイ}個、そのうち3の倍数でないものは{ウエ}個、3の倍数でな
   い約数の総和は{オカキ}
   1～200までの中に、40より大きな5の倍数の数は{クケ}個あり、7の倍数は{コサ}個ある。
   1×2×3×4×5……×199×200＝Ｐとすると、Ｐは{シス}回7で割り切れ、{セソ}回14で
   割り切れる。

解答

...

(アイ)28　(ウエ)14　(オカキ)762　(クケ)32　(コサ)23　(シス)32　(セソ)32

解説

(アイ)

960=2^6*3*5より(6+1)(1+1)(1+1)=7*2*2=28個

(ウエ)

(6+1)(1+1)=14個

(オカキ)

(2^6+2^5+2^4+2^3+2^2+2+1)(5+1)=(2^7-1)*6=127*6=762

(クケ)

45≦5n≦200として9≦n≦40より40-9+1=32

(コサ)

42≦7m≦196として6≦m≦28より28-6+1=23

(シス)

これは、ちょっとした技をしっていないと難しいです。（[ ]はガウス記号です。)

[200÷7]=28,[200÷49]=4より32

(セソ)

Ｐの中の2の数は7よりも多いことは明らかであるから7の数だけ14で割り切れる。

よって32

NO.8-2　約数の総和２

問題

 45 名前：以下、名無しにかわりましてVIPがお送りします[] 投稿日：2009/03/30(月) 01:27:16.53 ID:vMqlMrlEO
  約数がちょうど28個である自然数のうち最小のものを求めよ

解答

...

960

解説

N=a^a'*b^b'*c^c'…とすると(a,b,c…はいずれも素数)

約数の個数が28個であることは

(a'+1)(b'+1)(c'+1)…=28

28=14*2,7*4,7*2*2の三通りが考えられてそのうちNが最小となるようにするには

なるべく大きい28の約数がなるべく小さい素数と対応すればいい。

∴N=2^13*3,2^6*3^3,2^6*3*5でこれらを比較してN=2^6*3*5。

よって、N=960