| NWU IUPC 2025 powered by CPS Academy |
|---|
| Finished |
You are given an array $$$a$$$ of $$$n$$$ positive integers $$$a_1,$$$ $$$a_2,$$$ ... $$$,a_n$$$. You are also given $$$m$$$ distinct primes $$$p_1,$$$ $$$p_2,$$$ ... $$$,p_m$$$.
It is guaranteed that every $$$a_i$$$ can be expressed as
That is$$$,$$$ all prime factors of all numbers are among these $$$m$$$ primes.
For any non-empty subset $$$S \subseteq \{1, 2, ..., n\},$$$ let gcd($$$S$$$) = gcd($$$a_i \; | \; i \in S$$$). That is, gcd(S) is the greatest common divisor of all elements of the array $$$a$$$ with their index in that subset.
Define a function $$$sf(x)$$$ – the squarefree part of an integer $$$x$$$ as the product of all distinct primes dividing $$$x$$$. For example:
Your task is to compute, the sum of squarefree parts of gcds over all non-empty subsets of $$$a$$$. Formally, you have to find the following value:
First line contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$), ($$$1 \leq m \leq 20$$$).
The second line contains $$$m$$$ space-separated integers $$$p_1,$$$ $$$p_2,$$$ ... $$$,p_m$$$ ($$$1 \leq p_i \leq 200$$$).
The third line contains $$$n$$$ space-separated integers $$$a_1,$$$ $$$a_2,$$$ ... $$$,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Output one integer, the required sum mod ($$$10^9 + 7$$$)
4 32 3 52 6 10 30
82
1 128
2
| Name |
|---|


