# B: ANDをとって引く解説

原案: bin、改変: Hec、解説: qLethon[(@pu__Ne)](https://twitter.com/pu__Ne)

何回操作を行っても全体のORをとった値は変わりません。したがって，「ORをとった値が全体のORになる集合」の要素の個数の最小値を$N$から引いた値が答えの上界になります。要素の個数が最小の集合$S$に含まれる数以外を$0$にすることはできるので、$N - |S|$が答えになります。

#### $|S|$の求め方
数列$B$を$B_i = |\{j \mid A_j = i\ (1 \le j \le N)\}|$と定めます。
このとき、
$$C_1 = B \\
C_{i, j} = \sum_{j = k | l} C_{i - 1,\ k}C_{1,\ l}$$
とすると、$C_{i, X} > 0$となる最小の$i$が$|S|$になります。($X$は全体のOR)

$C_{i - 1}$から$C_i$を求めるのは、下位集合のゼータ/メビウス変換を使うことで$O(\max(A)\log\max(A))$でできます。$|S|$は最大で$\lceil\log{\max(A)}\rceil$なので、全体として$O(N + \max(A)\log^2\max(A))$で解くことができます。