You are given $2n$ positive integers $x_i, d_i$ ($1 \leq i \leq n$). Let $l := [x_1, 2x_1, ..., d_1x_1, x_2, 2x_2, ..., d_2x_2, ..., x_n, 2x_n, ..., d_nx_n]$. Let $s = set(l)$, i.e., the set by deduplicating $l$. Please estimate the size of $s$, i.e., $|s|$, with respect to $\sum\limits_{i=1}^nd_i$.
For example, if $x_1 = 2, d_1 = 3, x_2 = 3, d_2 = 3$, then $l = [2, 4, 6, 3, 6, 9], s=\{2, 3, 4, 6, 9\}$, $d_1 + d_2 = 6$, $|s| = 5$.
This problem is open, you need to give a lower bound of $|s|$ as low as possible.
The motivation of this problem is algorithmic: Given a set $s$ and $n$ queries $q_1, q_2, ..., q_n$, for each query $q_i$, you need to find a least possible $x \in \mathbb{N}^{*}$ such that $q_i \mid x, x \notin s$. For example, if $s = \{1, 2, 4\}, q_1 = 3, q_2 = 2$, then the answers to $q_1$ and $q_2$ are $3$ and $6$, respectively. The complexity of a brute force algorithm is $\sum\limits_{i=1}^nd_i$, and I find it hard to estimate? I have considered the Principle of Inclusion and Exclusion (PIE).
Credit: Codeforces Round 830 DIV2D Balance.
