4338. [国家集训队 2026]三选二

【题目描述】

有 $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

【样例 1 输出】

8

【样例 2 输入】

1000000
114514 114
114514 810
200000 5

【样例 2 输出】

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\%$ 的分数。

原题共$139$组测试数据，COGS只有$100$组，剩余测试数据下载：第101-139组数据。

【来源】

IOI2026中国国家集训队集中培训 Day1 Task3