#P16115. [2026年山东集训一轮]数论题

    ID: 15326 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700数论莫比乌斯反演树状数组

[2026年山东集训一轮]数论题

题目描述

给定 T,n,mT,n,m,你需要回答 TT 次询问。每次询问给定 A,BA,B。

定义一个值域在 [1,m][1,m] 中的 nn 元组 a[1,n]a[1,n] 合法,当且仅当这 nn 个数满足:

gcd⁡(a1,a2,…,an)≤B,\gcd(a_1,a_2,\dots,a_n)\le B,

并且

lcm⁡(a1,a2,…,an)≥A.\operatorname{lcm}(a_1,a_2,\dots,a_n)\ge A.

定义一个 nn 元组的权值为:

∏iai.\prod_i a_i.

你需要求出所有合法 nn 元组的权值和。由于答案可能很大,请输出其对 998244353998244353 取模后的结果。

输入格式

第一行包含三个正整数 T,n,mT,n,m。

接下来 TT 行,每行包含两个正整数 A,BA,B。

输出格式

对于每次询问,输出一行一个整数,表示权值和对 998244353998244353 取模后的结果。

样例 1 输入

3 2 4
1 4
1 2
2 3

样例 1 输出

100
75
83

数据范围

对于所有数据:

  • 1≤T≤5×1051\le T\le 5\times 10^5;
  • 1≤n≤1091\le n\le 10^9;
  • 1≤A,B≤m≤3×1051\le A,B\le m\le 3\times 10^5。
测试点编号 T≤T\le m≤m\le 特殊性质
1∼21\sim 2 11 200200 无
33 10510^5 A
44 B
55 C
6∼76\sim 7 无
8∼98\sim 9 5×1035\times 10^3 3×1053\times 10^5 A
1010 B
1111 C
12∼1512\sim 15 无
16∼2016\sim 20 5×1055\times 10^5

特殊性质:

  • A:A=1A=1;
  • B:B=mB=m;
  • C:B=1B=1。