补题 （Multiples of 5）
来源：https://codeforces.com/gym/105231/problem/G
题目描述：
给定一个非负的长度小于 10的14次方的基数-11 整数，判断它是否是 5 的倍数。
由于输入规模较大，输入以 n 对的形式给出，其中每个对 (ai,bi) 代表 ai个连续的数字都是 bi。按顺序连接所有对得到输入数字。
这里我们使用数字 0,1,2,……,9 和字母 A 来表示基数-11 的数制。
例如，输入 (1,1),(4,5),(1,4) 表示数字 (155554)11。具体来说，十进制数 110 对应输入 (1,A),(1,0)。
输入
第一行包含一个整数 T(1≤T≤1000)，表示测试用例的数量。对于每个测试用例：
第一行包含一个正整数 n (1≤n≤100000)。
接下来的 nn 行每行包含一个正整数 ai(1≤ai≤1000000000) 和一个字符 bi(bi∈{0,1,2,…,9,A}，表示第 i对。
保证所有测试用例中 n的总和不会超过 100000。
注意数据不保证没有前导零。
输出
输出 T 行，第 i 行表示第 i个测试用例的答案。对于每个测试用例：
如果给定的基数-11 数是 5的倍数，则输出 "Yes"，否则输出 "No"。
不区分大小写，输出时不带引号。
示例
输入：
3
3
1 1
4 5
1 4
3
1 9
19 8
1 0
1
100 A
输出：
Yes
No
Yes
一、题目分析
本题要求判断给定的基数 - 11 整数是否为 5 的倍数。输入规模较大，以n对(a_i, b_i)的形式给出，其中a_i表示连续数字b_i的个数，b_i可以是0 - 9的数字或者字母A（在基数 - 11 中A表示 10 ）。通过按顺序连接这些对来得到要判断的数字。
二、解题思路
原理：在基数 - 11 下判断一个数是否为 5 的倍数，可利用数论中取模运算的性质。不需要完整地将基数 - 11 数转换为十进制数，因为判断是否为 5 的倍数只需要考虑该数对 5 取模的结果。
具体步骤
读取测试用例数量T 。
对于每个测试用例：
读取n ，表示数对的数量。
初始化一个变量sum为 0 ，用于累计计算过程中的值。
循环n次，每次读取a_i和b_i ：
如果b_i是A ，将其对应的数值 10 赋给k ；否则将b_i转换为对应的数值（b_i - '0' ）赋给k 。
因为a_i个连续的b_i ，根据数论性质，在求对 5 的模时，可以利用(a* b)%m = ((a%m)*(b%m))%m ，这里m = 5 。所以将k*a_i累加到sum中（计算过程中对 5 取模 ）。
最后根据sum对 5 取模的结果判断，如果结果为 0 ，输出"Yes" ，否则输出"No" 。
三、代码实现（C++）
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
#define ll long longint main() {ll T, n;ll a, k;char b;cin >> T;while (T--) {ll sum = 0;cin >> n;for (ll i = 1; i <= n; i++) {cin >> a >> b;if (b == 'A')k = 10;elsek = b - '0';sum = (sum + k * a) % 5; }if (sum % 5 == 0)cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}四、复杂度分析
时间复杂度：本题有两层循环，外层循环次数为测试用例数量T ，内层循环次数为每个测试用例中的数对数量n 。由于题目中T最大为10^3 ，所有测试用例中n的总和不超过10^5 ，所以总体时间复杂度为O(10^5) ，可以在规定时间内通过测试。
空间复杂度：程序中使用的额外空间主要是几个变量（如 T 、 n 、 a 、 k 、 sum 等 ），都是常数级别的，所以空间复杂度为O(1) 。