「THUSCH 2017」杜老师

ID: 5846

传统题

1000ms

256MiB

尝试: 1

已通过: 1

难度: 10

上传者:

杜传宇

标签>

数论、埃氏筛法、快速幂

题目描述

杜老师可是要打 $+\infty$ 年 World Final 的男人，虽然规则不允许，但是可以改啊！

但是今年 WF 跟 THUSC 的时间这么近，所以他造了一个 idea 就扔下不管了……

给定 $L,R$ ，求从 $L$ 到 $R$ 的这 $R-L+1$ 个数中能选出多少个不同的子集，满足子集中所有的数的乘积是一个完全平方数。特别地，空集也算一种选法，定义其乘积为 $1$ 。

由于杜老师忙于跟陈老师和鏼老师一起打 ACM 竞赛，所以，你能帮帮杜老师写写标算吗？

输入格式

从标准输入读入数据。

每个测试点包含多组测试数据。

输入第一行包含一个正整数 $T$ （ $1\le T\le 100$ ），表示测试数据组数。

接下来 $T$ 行，第 $i+1$ 行两个正整数 $L_i,R_i$ 表示第 $i$ 组测试数据的 $L,R$ ，保证 $1\le L_i\le R_i\le 10^{7}$ 。

输出格式

输出到标准输出。

输出 $T$ 行，每行一个非负整数，表示一共可以选出多少个满足条件的子集，答案对 $998244353$ 取模。

样例 1

样例输入

样例输出

16
16
947158782

样例说明

对于 $L=1,R=8$ ，对应的 $16$ 种选法为：空集 4 3, 6, 8 3, 4, 6, 8 2, 8 2, 4, 8 2, 3, 6 2, 3, 4, 6 1 1, 4 1, 3, 6, 8 1, 3, 4, 6, 8 1, 2, 8 1, 2, 4, 8 1, 2, 3, 6 1, 2, 3, 4, 6

样例 2

样例输入

6
3761870 4957871
2262774 4279409
3027437 5896884
3884310 5021632
3373244 5464739
5063504 5368121

样例输出

数据范围与提示

测试点	$R_i$ 的限制	$T$ 的限制	$\sum_{i=1}^T R_i-L_i+1$ 的限制	特殊约束
1, 2	$\le 30$	$\le 10$	$\le 10^{3}$	无特殊约束
3	$\le 10^{2}$			保证答案不超过 $5 \times 10^{6}$
4	$\le 10^{2}$			无特殊约束
5, 6	$\le 10^{3}$			$R_i-L_i\le 22$
7, 8				保证答案不超过 $2 \times 10^{6}$
9, 10			$\le 5,000$	无特殊约束
11, 12	$\le 10^{6}$		$\le 10^{7}$	$R_i-L_i\ge 999,990$
13, 14	$\le 10^{6}$			无特殊约束
15	$\le 10^{7}$	$\le 100$
16			$\le 2 \times 10^{7}$
17			$\le 3 \times 10^{7}$
18			$\le 4 \times 10^{7}$
19			$\le 5 \times 10^{7}$
20			$\le 6 \times 10^{7}$

#L2978. 「THUSCH 2017」杜老师

题目描述

输入格式

输出格式

样例 1

样例输入

样例输出

样例说明

样例 2

样例输入

样例输出

数据范围与提示

还没有账户？

登录