← 返回题目列表

AtCoder · abc349_f

I. 后续 LCM

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

给定一个正整数序列 A=(A_1,A_2,\dots,A_N) 长度 N 和一个正整数 M。求模数 998244353,非空且不一定连续的子序列 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