题目描述
对于整数 m≥2 和正整数 x,定义模 m 下 x 的阶 δm(x) 为最小的正整数 a,满足 xa≡1(modm)。
特别地,若这样的正整数 a 不存在,则 δm(x)=−1。
考虑另一个函数 fm(a),其中 m 为大于等于 2 的正整数、a 为正整数。令 fm(a) 表示模 m 意义下阶为 a 的剩余类个数,也就是满足 0≤x<m 且 δm(x)=a 的整数 x 的个数。
继续定义 g(m) 为所有 fm(a) 中的最大值,其中 a 为正整数。特别地,定义 g(1)=1。
初始时有一个变量 m=1,接下来进行 q 次操作。在每次操作中,你需要将 m 乘上或者除以一个质数,保证操作后 m 仍然为正整数。
请在每次操作后,求出当前 g(m) 的值。
由于答案可能很大,你只需要输出其对 998244353 取模后的结果。
输入格式
从文件 number.in 中读入数据。
第一行一个正整数 q,表示操作次数。
接下来 q 行,每行两个正整数 op,p,其中 op∈{1,2},且 p 为质数。
若 op=1,表示将 m 乘上 p;若 op=2,表示将 m 除以 p。
保证每次操作后 m 均为正整数。
输出格式
输出到文件 number.out 中。
输出 q 行,第 i 行一个非负整数,表示第 i 次操作后当前 m 对应的 g(m) 对 998244353 取模后的值。
样例 1
样例输入 1
6
1 2
1 3
1 2
2 3
1 5
2 2
样例输出 1
1
1
3
1
4
2
样例解释 1
每次操作后的 m 依次为 2,6,12,4,20,10。
以第三次操作后为例,此时 m=12。模 12 下,1 的阶为 1,5,7,11 的阶均为 2,其余剩余类的阶均不存在,因此 g(12)=3。
数据范围
对于所有测试数据:
- 1≤q≤5×105;
- 对于每次操作,op∈{1,2},2≤p≤107 且 p 为质数;
- 保证在每次操作后 m 均为正整数。
记每次操作后 m 的最大值为 maxm。在以下表格中,若一格留空则表示对应项没有额外限制。
| 测试点编号 |
q≤ |
maxm≤ |
特殊性质 |
| 1∼2 |
5×105 |
100 |
无 |
| 3∼4 |
2000 |
| 5∼6 |
105 |
| 7 |
106 |
| 8∼9 |
109 |
| 10 |
|
A |
| 11∼12 |
B |
| 13∼14 |
C |
| 15∼16 |
1000 |
D |
| 17 |
无 |
| 18∼19 |
105 |
D |
| 20∼21 |
无 |
| 22∼23 |
5×105 |
D |
| 24∼25 |
无 |
- 特殊性质 A:保证 m 始终可以被表示为 pk 的形式,其中 p 为质数,k 为非负整数;
- 特殊性质 B:保证 m 的不同质因子个数始终不超过 2;
- 特殊性质 C:保证 m 的不同质因子个数始终不超过 5;
- 特殊性质 D:保证每次操作中均有 op=1。