选择困难症
题目背景
Parviz 认为,如果一道题有一个可以显著优化复杂度的方法而不去使用,那这题就是有遗憾的。
Alice 认为,任何算法难度大于思维难度的题,出在正式比赛中都是没有意义的。
猫猫认为,ta 是学数学学的。
$\textsf{linyue}$ 认为……啊?你们在说啥?
很有喜剧效果的是这四个名字你可能都没法一下子对上号(
题目描述
Alice 与 Bob 在下棋之余,也需要一些娱乐活动来放松身心,比如去小吃街吃饭。作为一名绅士,Bob 每次都让 Alice 选择要去吃哪家。这却让 Alice 犯了难——她有选择困难症。
小吃街有 $n$ 家饭店,在第 $i$ 家就餐需要 $i$ 元钱。如果预算为 $a$ 元,则可以选择前 $a$ 家餐厅。
在长期的纠结后,Alice 想到一种方法:她提前在心里想好一个非负整数 $k< \text{lcm}_{i=1}^{n} i$ ,在得知预算 $a$ 之后,选择在第 $(k$ $\text{mod}$ $a)+1$ 家餐厅就餐。
由于买棋盘与棋子的市场价格浮动,每次就餐的预算未必相同,但都是 $[2,n]$ 之间的整数。Alice 想每次都换换口味,希望对于不同的 $a$,最后选定的餐厅各不相同。她想要知道满足要求的 $k$ 的个数,但又忙于与 Bob 下棋没有时间算,于是只好求助于你啦。
形式化地说,对于给定的 $n$,你需要求有多少个整数 $k \in [0, \text{lcm}_{i=1}^{n}i)$ ,满足 $k\bmod 2,k\bmod3 ,..., k\bmod n$ 各不相同。答案对 $998244353$ 取模。
输入输出格式
输入格式
第一行一个整数 $T$,表示共有 $T$ 组数据。
接下来 $T$ 行,每行一个整数 $n$ ,含义见题面。
输出格式
共 $T$ 行,每行一个整数,表示满足要求的 $k$ 的数量。
输入输出样例
输入样例 #1
3
3
4
5
输出样例 #1
4
3
6
输入样例 #2
5
13860108
13850709
220000633
693439571
1004535809
输出样例 #2
188051653
724253523
444803502
370347248
425186012
说明
**【样例解释1】**
$n=3,4$ 时,$k$ 的取值集合分别为 $\{2, 3, 4, 5\}$ 、 $\{3, 10, 11\}$。
$n=5$ 时:
| $k$ | $k \bmod 2$ | $k \bmod 3$ | $k \bmod 4$ | $k \bmod 5$ |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| $27$ | $1$ | $0$ | $3$ | $2$ |
| $34$ | $0$ | $1$ | $2$ | $4$ |
| $35$ | $1$ | $2$ | $3$ | $0$ |
| $39$ | $1$ | $0$ | $3$ | $4$ |
| $58$ | $0$ | $1$ | $2$ | $3$ |
| $59$ | $1$ | $2$ | $3$ | $4$ |
$\text{lcm}_{i=1}^{n}i=60$,可以验证在 $[0,60)$ 内不存在其他的 $k$ 满足条件,故答案为 $6$。
| 测试点编号 | $T \leq$ | $n \leq$ |
| -----------: | -----------: | -----------: |
| $1-2$ | $15$ | $15$ |
| $3-6$ | $1000$ | $1000$ |
| $7-12$ | $1000$ | $2 \times 10^7$ |
| $13-20$ | $15$ | $2 \times 10^9$ |
对于 $100\%$ 的数据,满足 $3 \leq n \leq 2 \times 10^9$,$ T \leq 1000$。