#P17723. [2026年福建省队集训]基础数论练习题

[2026年福建省队集训]基础数论练习题

题目描述

对于整数 m≥2m \ge 2 和正整数 xx,定义模 mm 下 xx 的阶 δm(x)\delta_m(x) 为最小的正整数 aa,满足 xa≡1(modm)x^a \equiv 1 \pmod m。

特别地,若这样的正整数 aa 不存在,则 δm(x)=−1\delta_m(x) = -1。

考虑另一个函数 fm(a)f_m(a),其中 mm 为大于等于 22 的正整数、aa 为正整数。令 fm(a)f_m(a) 表示模 mm 意义下阶为 aa 的剩余类个数,也就是满足 0≤x<m0 \le x < m 且 δm(x)=a\delta_m(x) = a 的整数 xx 的个数。

继续定义 g(m)g(m) 为所有 fm(a)f_m(a) 中的最大值,其中 aa 为正整数。特别地,定义 g(1)=1g(1) = 1。

初始时有一个变量 m=1m = 1,接下来进行 qq 次操作。在每次操作中,你需要将 mm 乘上或者除以一个质数,保证操作后 mm 仍然为正整数。

请在每次操作后,求出当前 g(m)g(m) 的值。

由于答案可能很大,你只需要输出其对 998244353998244353 取模后的结果。

输入格式

从文件 number.in 中读入数据。

第一行一个正整数 qq,表示操作次数。

接下来 qq 行,每行两个正整数 op,pop, p,其中 op∈{1,2}op \in \{1, 2\},且 pp 为质数。

若 op=1op = 1,表示将 mm 乘上 pp;若 op=2op = 2,表示将 mm 除以 pp。

保证每次操作后 mm 均为正整数。

输出格式

输出到文件 number.out 中。

输出 qq 行,第 ii 行一个非负整数,表示第 ii 次操作后当前 mm 对应的 g(m)g(m) 对 998244353998244353 取模后的值。

样例 1

样例输入 1

6
1 2
1 3
1 2
2 3
1 5
2 2

样例输出 1

1
1
3
1
4
2

样例解释 1

每次操作后的 mm 依次为 2,6,12,4,20,102, 6, 12, 4, 20, 10。

以第三次操作后为例,此时 m=12m = 12。模 1212 下,11 的阶为 11,5,7,115, 7, 11 的阶均为 22,其余剩余类的阶均不存在,因此 g(12)=3g(12) = 3。

数据范围

对于所有测试数据:

  • 1≤q≤5×1051 \le q \le 5 \times 10^5;
  • 对于每次操作,op∈{1,2}op \in \{1, 2\},2≤p≤1072 \le p \le 10^7 且 pp 为质数;
  • 保证在每次操作后 mm 均为正整数。

记每次操作后 mm 的最大值为 max⁡m\max m。在以下表格中,若一格留空则表示对应项没有额外限制。

测试点编号 q≤q \le max⁡m≤\max m \le 特殊性质
1∼21 \sim 2 5×1055 \times 10^5 100100 无
3∼43 \sim 4 20002000
5∼65 \sim 6 10510^5
77 10610^6
8∼98 \sim 9 10910^9
1010 A
11∼1211 \sim 12 B
13∼1413 \sim 14 C
15∼1615 \sim 16 10001000 D
1717 无
18∼1918 \sim 19 10510^5 D
20∼2120 \sim 21 无
22∼2322 \sim 23 5×1055 \times 10^5 D
24∼2524 \sim 25 无
  • 特殊性质 A:保证 mm 始终可以被表示为 pkp^k 的形式,其中 pp 为质数,kk 为非负整数;
  • 特殊性质 B:保证 mm 的不同质因子个数始终不超过 22;
  • 特殊性质 C:保证 mm 的不同质因子个数始终不超过 55;
  • 特殊性质 D:保证每次操作中均有 op=1op = 1。