「CSP 2019 十二月」魔数

(200-30) 分滚粗，T5 沉了，180 块钱白给。

数字恐惧症患者慎入

题目描述

已知五个数：

还有一个表达式

有一个长度为 的序列 ，初始时所有元素依次为从 到 的正整数，即 。

次查询，每次输入两个整数 ，你需要依次进行如下操作：

• 令 ；
• 输出 ；
• 令 的每个数都乘 。

样例

样例输入 1

4 4
1 3
3 4
3 3
1 3

样例输出 1

6
1105
1735
4744

样例 2

sample_magic.zip

数据范围及时空限制

时间限制：
空间限制：

题解

分解每个数得：

用 Python 算出 的循环节长度是 ， 的循环节长度是 。也就是说每个数的变化情况最多只有 种。

接着算：

根据上面的性质，我们只需要维护 就行了，并且只需要维护 个。因此维护 个状态，表示当前状态乘 个 和 个 后的情况是什么就好了。区间乘打标记顺便调整这些状态的取值即可。

我一 ICPC 选手为什么要打 CTF 啊

应该注意到：

时间复杂度：，其中 ，空间复杂度：。

代码见这里。