2月20日ブログ
今日学んだこと
- めんどくさい最小公倍数は切ることができる(記事に記載)
まえがき
やぁ、こんばんは、特に面白い前書きは思いつかないですね。
今日は、Eなんとかなんとかさんっていう高校生の方のブログを呼んで、水色に行くまでに何したら良いのかって言うのをだいたい学びました。 今後やることは以下の通りです
- STLの彼が紹介していたやつの問題を解く。
- 彼が紹介していた100問を解く。
こんな感じでSTLを使えるようになるっていうのと、基本的なアルゴリズムとデータ構造をマスターします。
ちなみにマスターしなきゃないデータ構造というのは３つあるらしくて、 木構造、グラフ、UnionFindだったかな。頑張るぞ〜
ABC150 D- Semi Common Multiple
[最小公倍数、式変形] 本番通せなくて(c++わい、敗北）、Python勢がオーバーフロー？ｗ知らんけどｗｗｗｗｗｗ みたい感じになって俺がブチ切れたやつ。
やっと今日解説動画を見ました。
ときかた
(mとMが出てきますが同じものです。どちらも入力で与えられる整数M);
とりあえず、LCMの奇数倍がM以下にナン個アレばいいかを求めればいいということがワカッタ。
しかし、オーバーフローするやん… ではどうするか
各a[i]について、全ての要素が2を素因数に持つ個数は同じでなければ行けない。
X = a'[i] * ( 2p + 1) //a'[i] = a[i]/2;
と言う式変形が出来て、Xは全てのa'[i]について共通で2p+1は奇数だから
各a[i]について、全ての要素が2を素因数に持つ個数は同じでなければ行けない。
そして、a[i]を2t (2tは、2のｔじょう。全てのa[i]は2tを約数に持つ。）で割る。 mも2tで割る
その上で、全部の最小公倍数を求める。 ここで大事なのが、 lcmを求める途中でlcmがM(入力で与えられるやつ）を超えた瞬間に、、ｌｃｍの倍数となるやつはM以下に無いので、0を出力して終わること(これを最小公倍数は切ることが出来る、みたいにテキトウに言いました
これで勝ち。
あとがき
今日は、14時ぐらいから22時ぐらいまで眠ちゃんをしていたので、2/20 AM6:00現在、めちゃくちゃおめめパッチりしています。
明日はホワイトボードが自宅に届くので楽しみです。
PCのお掃除をそろそろしないとな、と思っているのですがなかなか体が言うことを聞きませんね。 やるぞ！やるぞ！！
ちなみに、さっきテキトウに考えていた今月の目標は、春休み中に水色の問題をたくさん解けるようにする。って感じですかね。
そのための方法はまえがきのところで述べたように、強ツヨ高校生が示してくれた道に乗っかるだけ。
にゃうにゃう
