33OJ
登录 注册

#P17817. sum of floor(n/aiaj)

sum of floor(n/aiaj)

背景

本题为 P10704 加强版。

题目描述

给出 n,mn,m 和 nn 个整数 aia_i(1≤i≤n1\le i\le n)。

求:

$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}\left \lfloor \frac{m}{a_ia_j} \right \rfloor$$

输出答案对 998244353998244353 取模的结果。

输入格式

第一行两个整数表示 n,mn,m。

第二行 nn 个整数表示 a1,a2…ana_1,a_2\dots a_n。

输出格式

一行一个整数表示答案对 998244353998244353 取模后的结果。

5 30
2 2 8 4 2
88
10 5035239199
4853 53137 86933 4465 13588 11899 49877 16317 43326 52183
2715

提示

数据范围

1≤n≤3×1061\le n\le3\times10^6,1≤ai≤m≤10121\le a_i\le m \le10^{12}。

子任务编号 n≤n\le m≤m\le 分值
00 10610^6 101010^{10} 1010
11 ^ 101110^{11} 2020
22 3×1063\times10^6 4×10114\times10^{11} 3030
33 ^ 101210^{12} 4040