|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
一目問題を見て，「地道にやればできるな。」とは思ったものの，暗算ではちょっとキツそうだし，算チャレらしくないので，しばし考えました。 その結果，暗算でも容易な解法を思いつきました。 地道に数える解法を(解法1)に，暗算でできる解法を(解法2)に示します。 (解法1) 要するに，A = 2^10 * 3^10，B = A * A = 2^20 * 3^20 です。 そこで，B の約数は，m, n を 0 〜 20 の整数として 2^m * 3^n と書けます。 このうち，A の約数にならないのは，11 <= m <= 20 又は 11 <= n <= 20 となる場合です。 そして，A より小さいということから， ・11 <= m <= 20 の場合 2^11 * 3^0, ..., 2^11 * 3^9 の 10個。(3^0 = 1 < 2^1 = 2 < 3^1 = 3 なので。) 2^12 * 3^0, ..., 2^12 * 3^8 の 09個。(3^1 = 3 < 2^2 = 4 < 3^2 = 9 なので。) 2^13 * 3^0, ..., 2^13 * 3^8 の 09個。(3^1 = 3 < 2^3 = 8 < 3^2 = 9 なので。) 2^14 * 3^0, ..., 2^14 * 3^7 の 08個。(3^2 = 9 < 2^4 = 16 < 3^3 = 27 なので。) 2^15 * 3^0, ..., 2^15 * 3^6 の 07個。(3^3 = 27 < 2^5 = 32 < 3^4 = 81 なので。) 2^16 * 3^0, ..., 2^16 * 3^6 の 07個。(3^3 = 27 < 2^6 = 64 < 3^4 = 81 なので。) 2^17 * 3^0, ..., 2^17 * 3^5 の 06個。(3^4 = 81 < 2^7 = 128 < 3^5 = 243 なので。) 2^18 * 3^0, ..., 2^18 * 3^4 の 05個。(3^5 = 243 < 2^8 = 256 < 3^6 = 729 なので。) 2^19 * 3^0, ..., 2^19 * 3^4 の 05個。(3^5 = 243 < 2^9 = 512 < 3^6 = 729 なので。) 2^20 * 3^0, ..., 2^20 * 3^3 の 04個。(3^6 = 729 < 2^10 = 1024 < 3^7 = 2187 なので。) そこで，10 + 9 + 9 + 8 + 7 + 7 + 6 + 5 + 5 + 4 = 70 個 です。 ・11 <= n <= 20 の場合 2^0 * 3^11, ..., 2^8 * 3^11 の 9個。(2^1 = 2 < 3^1 = 3 < 2^2 = 4 なので。) 2^0 * 3^12, ..., 2^6 * 3^12 の 7個。(2^3 = 8 < 3^2 = 9 < 2^4 = 16 なので。) 2^0 * 3^13, ..., 2^5 * 3^13 の 6個。(2^4 = 16 < 3^3 = 27 < 2^5 = 32 なので。) 2^0 * 3^14, ..., 2^3 * 3^14 の 4個。(2^6 = 64 < 3^4 = 81 < 2^7 = 128 なので。) 2^0 * 3^15, ..., 2^2 * 3^15 の 3個。(2^7 = 129 < 3^5 = 243 < 2^8 = 256 なので。) 2^0 * 3^16 の 1個。(2^9 = 512 < 3^6 = 729 < 2^10 = 1024 なので。) 3^17 以上を因数に含むものは 0 個。(2^10 = 1024 < 3^7 = 2187 なので。) そこで，9 + 7 + 6 + 4 + 3 + 1 = 30 個 です。 以上ですべてなので，70 + 30 = 100 個 になります。 (解法2) B = A * A のとき，B の約数で A 以下のものの個数は ((B の約数の個数) + 1)/2 になります。 これは，次のようにして分かります。 C を A より小さい B の約数とすると，B/C も B の約数で，C < A なので，B/C = (A * A)/C = A * A/C > A となり， C を A より大きい B の約数とすると，B/C も B の約数で，C > A なので，B/C = (A * A)/C = A * A/C < A となり， A より小さい B の約数と A より大きい B の約数は１対１に対応しており，個数は同じです。 もちろん A も B の約数なので，B の約数で A 以下のものの個数は， ((B の約数の個数) - 1)/2 + 1 = ((B の約数の個数) + 1)/2 です。 これを使うと，今の場合，A = 2^10 * 3^10，B = A * A = 2^20 * 3^20 なので， (B の約数の個数) = (20 + 1)(20 + 1) = 21 * 21 = 441 (B の約数で A 以下のものの個数) = (441 + 1)/2 = 442/2 = 221 求めるのは，このうち A の約数でないものなので， (A の約数の個数) = (10 + 1)(10 + 1) = 11 * 11 = 121 を引いて，221 - 121 = 100 個 になります。 (A 自身を引いていることに注意。そこで，A より小さい B の約数になっています。) |
|
ネコの住む家
4月24日（金） 10:52:25
MAIL:uchi@sco.bekkoame.ne.jp 34374 |