15174：1〜199までの奇数の積の下3桁は？...クイズ ^^

問題15174・・・https://twitter.com/sansu_seijin/status/947816164763119616 より 引用 Orz〜

1から199までの奇数の積1×3×5×7×9×‥×197×199の下3けたの数はいくつですか。

解答

・わたしの...

3,5,7,9が20回...

3*5*7*9=945

945^2≡025

25^2≡625

625^2≡625

so..

((3*5*7*9)^8)^2*(3*5*7*9)^4

≡625*625

≡625 (mod 1000)

以下の計算でチェック...

200!/(2^100*100!)

=

♪

↑

嘘でした...^^; Orz...

↓

・鍵コメT様からのもの Orz〜

このやり方ではマズいと思います．
例えば1*3*5*7*9*11*13*15*17*19の下3桁は「075」であり，
945^2の下3桁「025」とは異なります．

*確かに...そうなりますわね...^^;

正の奇数aに対し，a以下の正の奇数すべての積をa!!と表します．
また，(10a+1)(10a+3)(10a+7)(10a+9)をf(a)と書くことにします．
f(a)=10000a^4+20000a^3+13000a^2+3000a+189なので，f(a)の下3桁は189です．

199!!=f(0)*f(1)*f(2)*…*f(19)*(5^20)*39!!
=f(0)*f(1)*f(2)*…*f(19)*(5^20)*f(0)*f(1)*f(2)*f(3)*(5^4)*7!!
≡(189^20)*(5^20)*(189^4)*(5^4)*1*3*5*7 (mod 1000).
(189^24)*1*3*5*7*(5^24)の下3桁を求めればよい．
5^3の(189^24)*1*3*5*7*(5^21)倍であり，
(189^24)*1*3*5*7*(5^21)を8で割った余りによって，下3桁は定まる．
(189^24)*1*3*5*7*(5^21)≡(5^24)*1*3*5*7*(5^21)≡(5^46)*3*7
≡(25^23)*21≡(1^23)*5≡5 (mod 8)
だから，求める下3桁は625．

*お願いして、も少し噛み砕いていただきました グラッチェ ^^v

式を短くするために関数fを導入しましたが，要するに
199!!=(1*3*7*9)*(11*13*17*19)*…*(191*193*197*199)*(5*15*25*…*195)
であり，5*15*25*…*195=(5*1)*(5*3)*(5*5)*…*(5*39)=(5^20)*39!!
ということです．同様に，
39!!=(1*3*7*9)*(11*13*17*19)*(21*23*27*29)*(31*33*37*39)*(5*15*25*35)
=(1*3*7*9)*(11*13*17*19)*(21*23*27*29)*(31*33*37*39)*(5^4)*1*3*5*7
ですね．

1*3*7*9や11*13*17*19は下3桁が189だから，
199!!≡(189^20)*(5^20)*(189^4)*(5^4)*1*3*5*7となることがわかります．

*5の倍数を取り出すのが...後半の推理に上手く使えるわけなのねぇ☆

but...思いつけないわ ^^;;

・鍵コメT様からの解説 グラッチェ〜m(_ _)m〜♪

(10a+1)(10a+3)(10a+5)(10a+7)(10a+9)を展開すると，
100000a^5+250000a^4+230000a^3+95000a^2+16890a+945となり，
1000で割った余りはaの値によっていろいろな値となってしまいます．
(スモークマンさんの方法でうまくいかない理由はこれであるとも言えます．)
因子(10a+5)を除けば，1000で割った余りが一定となり，うまくいきます．
これが5の倍数を除く理由です．

この手法は，「階乗の0以外の末尾の数字」でも利用される手法で，
実際に問題11599や問題12120で使われています．

問題11599 https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=11599&sk=0

問題12120 https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=12120&sk=0

*今まで...よくわからず読み流してましたぁ ^^;;v

[スモークマン]

＞1/3,4:02pmの鍵コメT様へ ^^
あれ...そうなるのか...^^;
so...わたしのではダメですね Orz...

>199!!=f(0)*f(1)*f(2)*…*f(19)*(5^20)*39!!
=f(0)*f(1)*f(2)*…*f(19)*(5^20)*f(0)*f(1)*f(2)*f(3)*(5^4)*7!!
≡(189^20)*(5^20)*(189^4)*(5^4)*1*3*5*7 (mod 1000).

こういう風に言えることがよくわかりませんです ^^;
もう少し噛み砕いていただければ幸いです〜m(_ _)m〜

[スモークマン]

＞6:05pmの鍵コメT様へ ^^
なるほど...了解できましたぁOrz
and..5の倍数をわざわざ別に考えられたのは...
125*8=1000
を使おうということと理解すればいいのでしょうか？
わたしには思いつけませんです...^^;...

紹介させていただきまっす〜m(_ _)m〜v

[スモークマン]

＞9:49pmの鍵コメT様へ ^^
1,3,7,9から3個選び出した積の和=1*3*5+1*3*7+1*7*9+3*7*9=300
になることは知りませんでしたわ...^^;v
問題11599,問題12120での解法もそこが肝でしたのねぇ ^^;;
今頃やっと気づけましたぁ^^;;☆
追記させていただきまっす〜m(_ _)m〜v