#P4900. 食堂

    ID: 3839 远端评测题 404ms 40MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>O2优化素数判断,质数,筛法前缀和逆元

食堂

题目背景

我CYJian就是死,死外边,从这跳下去,也不会吃食堂一口饭。

真香。。\color{white}\text{真香。。}

题目描述

食堂第ii天有ii道菜.CYJianCYJian觉得第ii天的第jj道菜的美味程度为{ij}\lbrace \frac{i}{j} \rbrace({}就是取小数部分),当然,CYJianCYJian是一个勇于尝试的人,所以每一道菜都会吃那么一点.

现在CYJian有TT个问题,每一个问题都是从第AiA_i天到第BiB_i天得到的美味值的总和.现在请你帮他算一算吧!请输出答案模998244353998244353的值.

输入格式

第一行一个数T。

接下来T行,每一行一共两个数,表示每一次询问的AABB

输出格式

T行,每行一个正整数表示美味值之和.如果答案可以表示成PQ\frac{P}{Q}的形式,则需要找到任意一个xx使得Q×xP(mod 998244353)Q \times x \equiv P (\bmod\ 998244353),并且输出xmod998244353x \bmod 998244353

1
1 3

499122177

提示

样例解释:第一天美味值为0.00,第二天美味值为0.00+0.00=0.00,第三天美味值为0.00+0.50+0.00=0.50,0.00+0.00+0.50=0.50=12\frac{1}{2},499122177×21(mod 998244353)499122177 \times 2 \equiv 1 (\bmod\ 998244353),所以答案为499122177.

数据范围:

数据点范围 TT= ABA\leqslant B \leqslant
151 \sim 5 11 50005000
6106 \sim 10 10610^6
101510 \sim 15 10610^6 50005000
162016 \sim 20 10610^6

注意: 本题捆绑测试