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 翻译