No.1731 Product of Subsequence
Problem Statement
You are given a sequence $A$ of $N$ positive integers. $A$ has $2^N-1$ non-empty subsequences. How many of them have a product of all elements that is a multiple of $K$? Print the count modulo $10^9+7$.
Input
$N\ K$ $A_1\ A_2\ \cdots\ A_N$
- $1\leq N\leq 2000$
- $1\leq K\leq 10^{9}$
- $1\leq A_i\leq 10^{18}$
- All input values are integers.
Output
Print the number of non-empty subsequences whose product is a multiple of $K$, modulo $10^9+7$.
Sample
Sample 1
Input
3 4 2 4 6
Output
5
The non-empty subsequences whose product of all elements is a multiple of $4$ are the following $5$: $(4),(2,4),(2,6),(4,6),(2,4,6)$.
Sample 2
Input
4 6 2 2 3 3
Output
9
The non-empty subsequences whose product of all elements is a multiple of $6$ are: $4$ of $(2,3)$, $2$ of $(2,2,3)$, $2$ of $(2,3,3)$, and $1$ of $(2,2,3,3)$.
Sample 3
Input
10 998244353 1 2 3 4 5 6 7 8 9 10
Output
0
Sample 4
Input
4 171654 141421356237 173205080756 223606797749 244948974278
Output
3
$A_i$ may not fit in a $32$ bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
とりゐ
tko919