103495: [Atcoder]ABC349 F - Subsequence LCM

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

问题描述

你被给定一个长度为 $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