AT_arc020_3 [ARC020C] A mod B Problem

在高桥君还是高中生的时候，他曾经参加过的竞赛中，曾经出过求两个整数之和的问题。对于最强最快的他来说，这样的问题简直是小菜一碟。 如今，高桥君已经成为大学生，正在和你一起参加面向大学生的竞赛。然而，他常用的编程语言所需的集成开发环境坏掉了，根本无法解题。因此，作为队友的你，决定在裁判组修复开发环境之前，代替他解决以下问题。 给定整数 $A$ 和 $B$，请输出 $A$ 除以 $B$ 的余数。这里，整数 $A$ 和 $B$ 具有如下特点： - 整数 $A$ 和 $B$ 都是十进制数。 - 在 $100$ 个测试点中，有 $99$ 个测试点满足 $B=1000000007(10^9+7)$。 - 整数 $A$ 非常大，并且部分具有周期性，其形式如下所述。 - 给定 $N$、$a_1,a_2,\ldots,a_N$ 和 $L_1,L_2,\ldots,L_N$，这表示整数 $A$ 由高位到低位依次重复 $a_1$ 共 $L_1$ 次，$a_2$ 共 $L_2$ 次，……，$a_N$ 共 $L_N$ 次拼接而成。 例如，当 $N=3,a=\{123,4,56\},L=\{2,2,1\},B=1000000007$ 时，$A=1231234456$，$A$ 除以 $B$ 的余数为 $231234449$。

输入通过标准输入给出，格式如下： > $N$ > $a_1\ L_1$ > $a_2\ L_2$ > $\vdots$ > $a_N\ L_N$ > $B$ - 第 $1$ 行给出一个整数 $N\ (1\leq N\leq 10,000)$，表示后续整数 $A$ 的信息长度。 - 接下来的 $N$ 行，每行给出整数 $a_i\ (1\leq a_i\leq 10^9)$ 和 $L_i\ (1\leq L_i\leq 10^9)$，用半角空格分隔。 - 第 $N+2$ 行给出整数 $B\ (1\leq B\leq 1,000,000,007)$。

请输出 $A$ 除以 $B$ 的余数，输出占一行，末尾需换行。

### 部分分 本题有 3 个数据集，每个数据集对应部分分。 - 若能通过 $L_1+L_2+\ldots+L_N\leq 100,000$ 且 $B=1000000007$ 的数据集 1，可获得 $20$ 分。 - 若能通过 $B=1000000007$ 的数据集 2（不包含上面的数据集 1），可获得 $79$ 分。 - 若能通过无额外限制的数据集 3，可获得 $1$ 分。 ### 样例解释 1 这是题目中的例子。 ### 样例解释 2 $A=123123123$。 ### 样例解释 3 该测试用例满足数据集 1、2、3 的限制。 ### 样例解释 4 该测试用例满足数据集 2、3 的限制。 ### 样例解释 5 该测试用例满足数据集 3 的限制。 由 ChatGPT 4.1 翻译