题目描述
有一个初值为 1 的整数 val。给定 n 个操作,第 i 个操作由 opti,ai 描述。
- 若 opti=0,将 val 改为 ai。
- 若 opti=1,将 val 改为 (val×ai)modp。
可以选择任意一部分操作,并按任意顺序执行,每个操作至多用一次。也可以不执行任何操作。求最终 val 有多少种不同的取值。保证 p 是质数。
输入格式
第一行两个整数 p,n。接下来 n 行,每行两个整数 opti,ai。
输出格式
一行一个整数,表示可能的不同取值的个数。
样例
19 3
0 5
1 7
1 17
7
原赛样例 2、3 见下发文件。
数据范围
0≤ai<p,opti∈{0,1}。原赛采用子任务捆绑测试。
| 原赛子任务 |
特殊限制 |
原赛分值 |
| 1 |
p,n≤3000 |
20 |
| 2 |
p,n≤50000 |
40 |
| 3 |
p≤200000,n≤1000000 |
原 PDF 题面