AdditionalFile5580.zip

#5580. 「北大集训 2025」三选二

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

有 $n$ 个格子，编号为 $0 \sim n-1$。初始时所有格子均为白色。

共进行三次染色，第 $i$ ($1 \le i \le 3$) 次染色会给定 $a_i, b_i$，满足 $0 \le b_i < a_i$，然后按照如下规则染色：

• 对于所有 $0 \le x < n$，若 $x \bmod a_i = b_i$，则将编号为 $x$ 的格子染为黑色。

三次染色后，求有多少不同的区间 $[l, r]$ 满足 $0 \le l \le r < n$ 且编号在 $l \sim r$ 内的格子均为白色。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示格子的数量。

输入的第 $i+1$ $(1 \le i \le 3)$ 行包含两个非负整数 $a_i, b_i$，表示第 $i$ 次染色给定的参数。

输出格式

输出到标准输出。

输出一行一个非负整数表示满足条件的区间数量对 $998,244,353$ 取模后的结果。

样例 1

输入

10
5 3
7 0
7 1

输出

8

样例 2

输入

1000000
114514 114
114514 810
200000 5

输出

136032633

子任务

对于所有测试数据，均有：

• $1 \le n \le 10^{13}$；
• 对于所有 $1 \le i \le 3$，均有 $0 \le b_i < a_i \le 2n$。

评分方式

对于每个子任务：

1. 正确回答所有满足 $a_1, a_2, a_3$ 两两互质的测试数据的答案，可获得该子任务 $60\%$ 的分数；
2. 正确回答所有测试数据的答案，可获得该子任务 $100\%$ 的分数