100 Doors
タスクの一覧で一番最初に載っていたので、試しにやってみた。
数字から始まる cargo package は作れないみたいなので "_100_doors" とした。
タスク概要
ドアが開いている時に閉じ、閉じている時には開く toggle という操作を考える。
一列に並んだ 100 枚の閉じたドアに対して、最初は全てのドアを toggle する。続いて 2 の倍数番目(2, 4, 6, ...)のドアを toggle, 3の倍数番目(3, 6, 9, ...)のドアを toggle していき、100 番目のドアのみを toggle するまで繰り返す。
最終的にドアの開閉状態はどうなっているかを出力する。
方針
単純に 2 重ループを回す。
余談
タスクのページにも書いてあるけど、結果を見るとドアは平方数の場合のみ開いていて、他は閉じている。
最終的なドアの状態は、約数の数の偶奇で決まり、
- 偶数: 閉
- 奇数: 開
となる。つまり、約数の数は平方数のみ奇数になるようだ。
なぜそうなるのかを考えてみると、基本的に約数はペアで出現する(18 なら 1-18, 2-9, 3-6, といった具合)。ペアにならないケースは同一数をかけ合わせた時で、そうした約数が存在するということは平方数であることを意味する。