E. Add Modulo 10 - 题解

比赛与标签

比赛: Codeforces Round 811 (Div. 3) 标签: brute force, math, number theory 难度: *1400

题目大意喵~

主人你好呀！这道题是这样的喵~

我们有一个装着 n 个整数的数组 a。我们可以对数组里的任何一个数字 a[i] 进行一种神奇的操作，任意次都可以哦！这个操作就是把 a[i] 变成 a[i] + (a[i] % 10)。

我们的任务是判断，通过这些操作，能不能让数组里所有的数字都变得一模一样呢？如果可以，就输出 "Yes"，不然就输出 "No"，的说。

举个栗子：数组是 [6, 11]。

我们对 a[1] = 6 操作一下，6 % 10 = 6，所以 6 变成了 6 + 6 = 12。数组现在是 [12, 11]。
接着我们对 a[2] = 11 操作一下，11 % 10 = 1，所以 11 变成了 11 + 1 = 12。数组现在是 [12, 12]。哇！所有数字都变成 12 了，所以答案是 "Yes" 呐！

解题思路大揭秘！

这道题看起来操作很神秘，但只要我们仔细观察一下，就能发现其中的规律啦，喵~ 关键就在于数字的个位数！

让我们来追踪一下，一个数字在连续操作下，它的个位数会怎么变化：

个位是 0: x + (x % 10) = x + 0 = x。数字再也不会变了，它到达了终点站！
个位是 5: x + (x % 10) = x + 5。新数字的个位数一定是 0。然后就和上面一样，到达终点站啦。
个位是 2, 4, 6, 8:
- ...2 -> ...2 + 2 = ...4
- ...4 -> ...4 + 4 = ...8
- ...8 -> ...8 + 8 = ...6
- ...6 -> ...6 + 6 = ...2 发现了吗？它们进入了一个 2 -> 4 -> 8 -> 6 -> 2 的循环！就像一趟永远不会停歇的循环列车，喵~
个位是 1, 3, 7, 9:
- ...1 -> ...1 + 1 = ...2 (上车了！)
- ...3 -> ...3 + 3 = ...6 (上车了！)
- ...7 -> ...7 + 7 = ...4 (上车了！)
- ...9 -> ...9 + 9 = ...8 (上车了！) 这些数字经过一两次操作，也都会进入上面那个 2 -> 4 -> 8 -> 6 的循环列车。

根据这个发现，我们可以把所有数字分成两大类：

“终点站”家族：初始个位数是 0 或 5 的数字。经过若干操作后，它们的个位数一定会变成 0，然后就不再变化。
“循环列车”家族：所有其他数字。经过若干操作后，它们都会进入 2 -> 4 -> 8 -> 6 的循环。

要让所有数字相等，它们必须能够到达同一个值。但是，“终点站”家族的数字最终只能停在个位是 0 的数上，而“循环列车”家族的数字永远在个位是 2, 4, 6, 8 的数之间徘徊。它们永远无法相遇！

所以，我们得出了第一个重要结论： 如果数组里同时存在“终点站”家族和“循环列车”家族的数字，那么它们永远不可能相等。答案一定是 "NO"。

那么，如果数组里只有一种家族的数字呢？

情况一：数组里全是“终点站”家族的数字 (个位都是 0 或 5)

我们可以把所有个位是 5 的数 x 都操作一次，变成 x+5，这样它的个位就变成 0 了。
个位是 0 的数不需要操作。
经过这样处理后，所有数字的个位数都变成了 0，它们都不会再变了。
这时，我们只需要检查一下，现在数组里所有的数是不是都相等。如果相等，答案就是 "YES"，否则就是 "NO"。

情况二：数组里全是“循环列车”家族的数字

这一族的所有数字，最终都会进入 2 -> 4 -> 8 -> 6 的循环。
为了让它们有相等的可能性，我们先把每个数 a[i] 都操作到它刚好进入循环的那个点，也就是个位变成 2 的时候。
现在，所有数字的个位数都是 2、4、6 或 8，并且它们都在同一条“轨道”上。
我们观察一下这个循环：...2 (+2) -> ...4 (+4) -> ...8 (+8) -> ...6 (+6) -> ...2。一整个循环下来，数字总共增加了 2 + 4 + 8 + 6 = 20。
这意味着，如果两个在循环中的数字 x 和 y 可以变得相等，它们一定可以通过若干个完整的 +20 循环来追上对方。比如，如果 x 和 y 的个位数相同（都在循环的同一点），那么它们的差值必须是 20 的倍数，才能保证 x 可以通过若干次完整的循环变成 y。
于是，我们的策略是：
1. 把每个数 a[i] 都通过操作变换，直到它的个位数变成 2（或者 4, 6, 8，只要是循环中的一个就行，为了统一，我们都变到个位是 2）。
2. 得到新的数值后，我们检查任意两个数（比如 a[i] 和 a[0]）的差值是否是 20 的倍数。
3. 如果所有数的差值相对于 a[0] 都是 20 的倍数，说明它们在同一条“循环轨道”上，并且“圈数”差距是整数，可以通过操作变得相等。答案是 "YES"。
4. 否则，就是 "NO"。

总结一下策略就是：

先检查数组里有没有个位是 0 或 5 的数。
如果有，就按 情况一 处理。
如果没有，就按 情况二 处理。

这样问题就迎刃而解啦，喵~

代码实现喵~

cpp

#include <iostream>
#include <vector>
using namespace std;

// 这个函数会把一个数不断操作，直到它的个位数变成 2 或 0
// 这是“循环列车”家族上车的地方，或者是“终点站”家族的终点站
int transform(int x) {
    while (x % 10 != 2 && x % 10 != 0) {
        x += x % 10;
    }
    return x;
}

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        bool has05 = false; // 用来标记数组里有没有“终点站”家族的成员

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] % 5 == 0) { // 个位是0或5的数，对5取模都为0
                has05 = true;
            }
        }

        // 情况一：如果存在“终点站”家族的成员
        if (has05) {
            // 先把所有个位是5的数都变成个位是0的数
            for (int i = 0; i < n; i++) {
                if (a[i] % 10 == 5) {
                    a[i] += 5;
                }
            }
            // 现在所有“终点站”家族的数都到了终点，不会再变了
            // 检查它们是否都相等。同时也检查了有没有混入“循环列车”家族的数
            // 如果混入了，它们的值肯定和“终点站”家族的不一样
            bool allEqual = true;
            for (int i = 1; i < n; i++) {
                if (a[i] != a[0]) {
                    allEqual = false;
                    break;
                }
            }
            cout << (allEqual ? "YES" : "NO") << '\n';
        } 
        // 情况二：数组里全是“循环列车”家族的成员
        else {
            // 把每个数都操作到循环的某个统一状态
            for (int i = 0; i < n; i++) {
                a[i] = transform(a[i]);
            }
            // 检查它们是否都在同一条“轨道”上，即差值是否为20的倍数
            bool sameMod = true;
            for (int i = 1; i < n; i++) {
                // 如果个位数都是2，那么差值必须是20的倍数才能相等
                if ((a[i] - a[0]) % 20 != 0) {
                    sameMod = false;
                    break;
                }
            }
            cout << (sameMod ? "YES" : "NO") << '\n';
        }
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N) 的说。对于每个测试用例，我们最多遍历数组两三次。transform 函数里的 while 循环对于每个数字最多只会执行几次（比如个位是1，1->2，一次；个位是3，3->6->2，两次），所以可以看作是常数时间 O(1)。因此，总的时间复杂度是线性的，与数组大小 N 成正比。
空间复杂度: O(N) 的说。我们主要用了一个 vector 来存储输入的数组，所以空间复杂度和数组大小 N 成正比。

知识点与总结

这道题真有趣，不是吗？它教会了我们几件重要的事情呐：

分类讨论是好朋友：当一个问题看起来有很多种可能性时，尝试根据某些关键性质（比如这里的个位数）将问题分成几个更简单的小问题来解决，这是一种非常强大的思维方式！
寻找规律与周期：对于不断迭代的操作，一定要有耐心去手动模拟几步，看看会不会出现不动点（像个位是0的数）或者循环（像 2-4-8-6 循环）。这常常是解题的突破口！
模运算的妙用：% 运算符不仅能取余数，还能帮我们判断周期性。 (a - b) % 20 == 0 这个小技巧，简洁地判断了两个在同个循环周期里的数能否通过操作相等，非常优雅！

希望这篇题解能帮助到你，主人！继续加油，享受解题的乐趣吧，喵~ ✨

E. Add Modulo 10 - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​