2021/02/08
GCD or MIN
黄diff
残る整数は，A[0]...A[N-1]から1個以上取ってgcdを行った形で表せて、Aの最小値以下のもの。A[0]...A[N-1]のそれぞれの約数(残る整数の候補)を求めて、それらが↑の形で表せるかを判定することで解くのを思いついた。判定は、例えばxを考えるとき、A[0]...A[N-1]の中でxの倍数の集合のgcdがxになればokでよさそう。1e9以下の自然数の約数の個数の最大が1344らしいので，多めに見積もって1344*N*Nのループが必要になる。間に合うか怪しかったので解説を見た。
解説は自分の方法と本質的には同じで、より高速化したものだった。連想配列を用意して、A[i]%x==0ならmap[x]=gcd(map[x],A[i])をする。候補の列挙と判定を同時に行っている感じ。
Two Sequences
黄diff
ibit目を考える。このとき、aとbの値はi+1bit目以降は無視していい。t=(1<<i)とする。i+1bit目以降は無視した値でのaとbの値の和は[0,4t)になる。この中で、ibit目が1になるのは[t,2t),[3t,4t)。ajを固定して、にぶたんで和がibit目が1になるbの個数を数える。
安全点検
JOI 難易度7
にぶたん。後ろから必要な人数を求めていく。
その他
明日は課題のb+-treeを実装する。
