最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • Count GCD

    正文概述 陈老师   2026-01-20 15:14:52  

    题目描述

    给定两个整数 nn 和 mm,以及一个长度为 nn 的数组 aa。对于每个 1≤i≤n1 \le i \le n,都有 1≤ai≤m1 \le a_i \le m。

    你的任务是计算有多少个不同的长度为 nn 的数组 bb 满足以下条件:

    • 对于每个 1≤i≤n1 \le i \le n,都有 1≤bi≤m1 \le b_i \le m;
    • 对于每个 1≤i≤n1 \le i \le n,都有 gcd⁡(b1,b2,b3,…,bi)=ai\gcd(b_1, b_2, b_3, \ldots, b_i) = a_i。

    这里 gcd⁡(a1,a2,…,ai)\gcd(a_1, a_2, \dots, a_i) 表示整数 a1,a2,…,aia_1, a_2, \ldots, a_i 的最大公约数。

    由于答案可能很大,请输出答案对 998 244 353998\,244\,353 取模后的结果。

    输入格式

    每组测试数据包含多组测试用例。第一行包含一个整数 tt(1≤t≤1001 \le t \le 100)——表示测试用例的数量。接下来是每组测试用例的描述。

    每组测试用例的第一行包含两个整数 nn 和 mm(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5,1≤m≤1091 \le m \le 10^9)——数组 aa 的长度和元素的最大可能值。

    每组测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤m1 \le a_i \le m)——数组 aa 的元素。

    保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

    输出格式

    对于每个测试用例,输出一个整数,表示满足条件的不同数组的数量。由于答案可能很大,请输出对 998 244 353998\,244\,353 取模后的结果。

    样例

    5
    3 5
    4 2 1
    2 1
    1 1
    5 50
    2 3 5 2 3
    4 1000000000
    60 30 1 1
    2 1000000000
    1000000000 2
    
    3
    1
    0
    595458194
    200000000
    

    提示

    样例1解释

    在第一个测试用例中,可能的数组 bb 有:

    • [4,2,1][4,2,1];
    • [4,2,3][4,2,3];
    • [4,2,5][4,2,5]。

    在第二个测试用例中,唯一满足条件的数组是 [1,1][1,1]。

    在第三个测试用例中,可以证明不存在满足条件的数组。

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » Count GCD