年末年始の連休初日からインフルエンザ（A)と診断されてしまいました。勉強がはかどりそうです（涙）
追記
インフルなめてましたすいませんでした。勉強捗るわけありませんでした。これ冗談抜きで死んでもおかしくないんじゃないかってレベルの辛さあります
高熱が続くと脳障害を起こすとか聞きますし、それも不安です。これ以上頭悪くなりたくない…ﾎﾞｽｹﾃ
いま「マスター・オブ・整数」をやっています。
約数の個数を利用する問題で競プロっぽい面白い問題がありました。ちなみにネタバレを含みます。
問題
1～200まで,1から200までの整数を表にかいたカードが並べられている. このカードに全て表の状態からはじめて次の200個の操作をする.
操作1. 1の倍数のカードをすべてひっくりかえす.
操作2. 2の倍数のカードをすべてひっくりかえす.
.
.
.
操作n. nの倍数のカードをすべてひっくりかえす.
.
.
.
操作200. 200の倍数のカードをすべてひっくりかえす.操作が終了したとき,表向きになっているカードは何枚あるか.
問題文からして競プロっぽさがすごいです。
解き方
例えば42が操作終了後どうなっているか考えてみます。
42の約数は8個あり、偶数回ひっくりかえすことになるので操作終了後は表になっていることがわかります。
もしこれが競プロなら約数の数が偶数なら表、奇数なら裏ということで1..NまでならO(N)で求められますね。
ただし今回はコンピュータを使うわけではなく200回紙に書くわけにはいかないので、どういう数であれば約数の数が奇数になるのかを考える必要があります。
まずはある数の約数の数を求めかたを思い出します。 ある数を素因数分解したときに
Ap * Bq * Cr ...
と表すとき、約数の個数は
(p+1)(q+1)(r+1)...
で求められます。
ここで、p, q, r ... がすべて偶数の場合に約数の個数が奇数になることがわかります。
で、p, q, r ...がすべて偶数の場合とはどういう場合なのかというと、
22 = 4 や
22 * 32 = 36 や
26 = 64 などがそうで、
これらは平方数になります。
1..200のうち、約数の個数が奇数のものは、12, 22, ... 142 で14個、約数の個数が偶数のものは200 - 14 = 186ということで、操作終了後に表になっているカードの枚数は186枚になります。
Atcoderで出題されるとしたら300点くらいでしょうか。
以前は約数の個数だとか倍数の判定だとかは無味乾燥なイメージがあってあまり興味が湧かなかったんですが、競プロに使えるかもしれないと考えるとやる気が出ます。
