103495: [Atcoder]ABC349 F - Subsequence LCM
Description
Score: $525$ points
Problem Statement
You are given a sequence of positive integers $A=(A_1,A_2,\dots,A_N)$ of length $N$ and a positive integer $M$. Find the number, modulo $998244353$, of non-empty and not necessarily contiguous subsequences of $A$ such that the least common multiple (LCM) of the elements in the subsequence is $M$. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences. Also, the LCM of a sequence with a single element is that element itself.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq M \leq 10^{16}$
- $1 \leq A_i \leq 10^{16}$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
4 6 2 3 4 6
Sample Output 1
5
The subsequences of $A$ whose elements have an LCM of $6$ are $(2,3),(2,3,6),(2,6),(3,6),(6)$; there are five of them.
Sample Input 2
5 349 1 1 1 1 349
Sample Output 2
16
Note that even if some subsequences coincide as sequences, they are distinguished if they are taken from different positions.
Sample Input 3
16 720720 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Sample Output 3
2688
Input
Output
问题描述
你被给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 和一个正整数 $M$。找出序列 $A$ 中非空且不一定是连续的子序列的数量，使得子序列中元素的最小公倍数（LCM）为 $M$。如果两个子序列是从序列的不同位置取出来的，即使它们作为序列相同，也被视为不同的子序列。此外，只有一个元素的序列的 LCM 是该元素本身。
限制条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq M \leq 10^{16}$
- $1 \leq A_i \leq 10^{16}$
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印答案。
样例输入 1
4 6 2 3 4 6
样例输出 1
5
序列 $A$ 中元素 LCM 为 $6$ 的子序列有 $(2,3)$, $(2,3,6)$, $(2,6)$, $(3,6)$, $(6)$; 共有五个。
样例输入 2
5 349 1 1 1 1 349
样例输出 2
16
注意，即使某些子序列作为序列相同，但如果它们来自不同的位置，它们也被视为不同。
样例输入 3
16 720720 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
样例输出 3
2688