1兆までの数字を掛け算して、末尾の0を取り除いた下5桁を答えなさいという問題です。
計算式自体はかなり簡単です。ただ、1兆まで順に掛け算するのはあまりにも大変そうです。
下5桁が対象なので、100001は1と同じ扱いになり、繰り返しで計算できそうですが、110000は11になるので、単純には繰り返せばよいというわけではありません。
5の倍数も気になります。5×2は10なので、これは1と同じ扱いになります。
7×11×13=1001か、、、3×9×37＝999か、、、この二つを掛けたら999999、これが２つそろって、掛け算できたら1だよな。。。みたいなことを考えているうちに、ちょっと違うアプローチを思いつきました。
なので、この下5桁は明らかにx^4です。これは
まで同様に計算できるのですが、前述の通り、xが10の倍数の場合は、成り立たないことが明らかなので、最初から5の倍数を除外することにします。
1000単位で繰り返して計算できるので、
5の倍数を除外した、1から499を掛け算して下5桁を取った値をｇ(499)として考えることにします。
また、5の倍数を除外したもので考えると、末尾の0を切り捨てる処理がなくなり、
1000000000001から1000000000499の積は1から499の積と同じになります。
この計算で、上限からはみ出してしまう値が、考慮できていていない最初の値と同じになるというところがポイントです。
1000000000000に5の倍数は200000000000個あり、g(499)は2000000000個あり、ちょうど100倍違うので、
とすると
と計算できることになります。
(1000+x)(1000+y)＝1000000+1000(x+y)+xyなので、
本当はf(2560000)の先をそのまま計算するのはまずいのですが、５を取り除いた1から499までを足すと末尾が0になるので、もう一桁大丈夫です。2100で割っているところが少し気になりますが、Gの要素の和を計算すると末尾はちゃんと0になってました。
ここで、F(a,b)をaからbまでの積として考えることにします。
そうするともう少し計算を継続することができ、
となります。最後にGのべき乗の計算が残るのですが、なんと
G26＝Gとなります。つまり、
となり、掛け算をする回数は8500回程度で済むことになります。
もう少しまじめに考えるとさらに減らせるはずなのですが、これくらいならなんなく計算できると思います。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
f(4000)=G5・f(500)・F(2501,4000)ですので、
＝G10・f(500)・F(2501,4000)・F(100001,102000)・F(510001,512000)
＝G11・f(100)・F(2501,4000)・F(100001,102000)・F(510001,512000)
さらに、
F(100001,102000)＝F(100001,100500)・F(100501,101500)・F(101501,102000)
F(510001,512000)＝F(510001,510500) ・F(510501,511500) ・F(511501,512000)
であり、
F(100501,101500)・F(510501,511500)＝G４・F(20101,20300)・F(102101,102300)
とすることができます。
その結果、
＝G15・f(100)・F(2501,4000)・F(100001,100500)・F(20101,20300)・F(101501,102000)
・F(510001,510500) ・F(102101,102300)・F(510501,512000)
とすることができます。
1兆個が5000個ぐらいまで減りました。
ー－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
ここまでやって、気が付きました。
f(2560000)からf(512000)への変換ができるのなら、
(100+x)(100-x)(200+x)(200-x)でも成り立つということです。
実際にやってみると、これでも計算できて、掛け算の回数は1000回弱になります。
1から49までの数から5の倍数を除いた数を掛け算した下5桁の値を210で割った値をHとして、
H239・f(130)・F(102371,102390)・F(511951,512000)・F(20451,20470)・F(102351,102370)・F(4051,4090)・F(651,810)
で、掛け算の回数は718回ということになりました。