Codeforces Round #846 (Div. 2)

　Cが出題ミスでunratedになった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #846 (Div. 2) Cが分からずDに行き、Dが解けたところでunratedになりやる気を失った。
A 奇数三個 or 偶数二個と奇数一個
B 二つに分けるのがベスト
D 下の桁から決める。1を引いたときcntが減ったらそこは1だった、そうでなければ0だったと分かる

— titia (@titia_til) January 25, 2023

F. Three Chairs

　自力AC。

・各iについて、「gcdがiの倍数になる組み合わせ」を求める。

・上で求めたものをSCOREという配列とすると、j : iの約数 に対してSCORE[j]-=SCORE[i]　というのを大きい数から行う。これで、SCOREという配列が、「gcdがiになる組み合わせ数」となる。

　という流れ。

　大体こういう流れだとは思ったのだが、一つ目のやり方が分からず時間がかかってしまった。SUM[i]で、i以下に存在するAの個数とすると、

　iの倍数についてi, 2*i, 3*i, ...　と調べていくとき、

・j in Aであるようなjが何回登場したか

・それらについてのSUM[j]の和

　をもっていればSCOREを計算できる。