Subsequence LCM

题目描述

给你一个正整数序列 $A=(A_1,A_2,\dots,A_N)$（长度为 $N$）和一个正整数 $M$。求非空且不一定连续的子序列的数量（对 $998244353$ 取模），使得该子序列中元素的最小公倍数（LCM）为 $M$。如果两个子序列取自序列中的不同位置，即使作为序列它们相同，也被视为不同的子序列。另，单个元素序列的 LCM 就是该元素自身。

输入格式

输入由标准输入给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

4 6
2 3 4 6

5

5 349
1 1 1 1 349

16

16 720720
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

2688

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq M \leq 10^{16}$ $1 \leq A_i \leq 10^{16}$ 所有输入值均为整数。序列 $A$ 中元素的 LCM 为 $6$ 的子序列有 $(2,3),(2,3,6),(2,6),(3,6),(6)$；共有五个。
注意即使某些子序列作为序列相同，只要取自不同位置也被视为不同子序列。

标签: AtCoder|abc349F

来源

AtCoder|abc349F