P2429 Silly Problem

Find the sum of all natural numbers not exceeding $m$ whose set of prime factors intersects the given set of primes.

The first line contains two integers $n, m$. The second line contains $n$ integers $p_i$, representing the elements of the prime set.

Output one integer, the answer modulo $376544743$.

Sample explanation: All qualifying numbers are $3, 5, 6, 9, 10, 12, 15$, and their sum is $60$. | Test point ID | Constraints | |:-:|:-:| | $1 \sim 3$ | $n m \le {10}^7$ | | $4 \sim 5$ | $n \le 2$，$m \le {10}^9$ | | $6 \sim 7$ | $n \le 20$，$m \le {10}^8$ | | $8 \sim 10$ | $n \le 20$，$m \le {10}^9$ | For the first $30\%$ of the testdata, $1 \le n, m$. For the remaining $70\%$ of the testdata, $1 \le n \le 20$，$1 \le m \le {10}^9$. Translated by ChatGPT 5