2004-01-01 (木)
*元旦と階乗
あけましておめでとうございます．今年もよろしくお願いします．
書く事が無いので，昨日の問題の解答とか．とりあえず，「n! = 2^a1 * 3^a2 * 5^a3 * 7^a4 * 11^a5 * …」と，素因数分解して，明らかにa1＞a3であるので(これくらいは許してください)，「n! = 2^(a1-a3) * 3^a2 * 5^0 * 7^a4 * 11^a5 * … * 10^a3」とできます．ここで，「10^a3」で割ると，n!の末端の0が全部消えます．そうなると，問題の場合は，１の位は「5」になってますが，n!/10^a3が5の倍数になることは無いので，この式を満たす自然数nは存在しません．ちなみに，昨日の「304888344611713860501505000000」は，28の階乗に1000000を足した値です．この問題から，n!の0を除いた一番下の桁が5になることがないということが分かりますね．さらに，a3さえ求めれば，終わりに0がいくつ付くかも求められます．意味は無いですが…．そういえば，大きな数の階乗の終わりに付く0の数を求める問題がずっと前の数学オリンピックの問題にあったと思います．
なんだか，MD5は面倒くさそうであまり理解してなかったのですが，改めてRFC1321を読んで見ると，結構シンプルなアルゴリズムでした．せっかくなので，HSPで書いてみる．マクロを多用して実装すると，最適化の無いHSPでは極端に効率が悪くなりそうだったので，なるべく効率が良くなるように．というか，HSPのコードの最適化ツールが欲しいかも．不要な括弧と，定数部分くらいはコンパイル時にどうにかしてほしいなぁ．あと，使わないモジュールとかも自動で切り離して欲しいし．というわけで，サンプルスクリプト置き場にモジュールを追加．そもそも，サンプルスクリプト置き場って，ずいぶん分かりにくいとこにあって，たどり着く人が少ないような気がする…．