喵~ 主人，今天我们来看一道超级有趣的题目，Codeforces 1985B - Maximum Multiple Sum！这道题就像是在一堆毛线球里找最大最暖和的那个，只要有耐心，就一定能找到的啦~ 让我们一起来看看吧！🐾

题目大意

题目是这样哒：给我们一个整数 n，我们需要在 2 到 n 之间找一个整数 x。

我们的目标是，让 x 的所有不超过 n 的倍数（也就是 x, 2x, 3x, ... 一直到 kx <= n）加起来的总和最大。最后，我们只要告诉裁判，那个能让总和最大的 x 是多少就可以啦！

举个栗子🌰，如果 n=3，那么 x 可以是 2 或者 3。

• 当 x=2 时，不超过 3 的倍数只有 2，总和就是 2。
• 当 x=3 时，不超过 3 的倍数只有 3，总和就是 3。 因为 3 > 2，所以最优的 x 就是 3 啦，是不是很简单喵？

题解方法

看到这道题，特别是注意到 n 最大也只有 100，本喵的猫耳朵立刻就竖起来了！这么小的数据范围，简直是在邀请我们使用最简单直接的方法——暴力枚举！没错，就是把所有可能的 x 都试一遍！

思路是这样滴：

1. 我们就从 x=2 开始，一直试到 x=n。
2. 对于每一个 x，我们都去计算一下它的倍数之和。比如说，对于当前的 x，我们就把 x, x+x, x+x+x... 所有小于等于 n 的数都加起来，得到一个 current_sum。
3. 我们用一个变量 max_sum 来记录目前为止找到的最大和，再用一个 best_x 来记录是哪个 x 得到了这个最大和。
4. 每次算出一个新的 current_sum，就和 max_sum 比较一下。如果 current_sum 更大，那我们就找到了一个新的“候选猫王”！赶紧更新 max_sum = current_sum 和 best_x = x。
5. 等我们把从 2 到 n 所有的 x 都检查完，best_x 里存的就是我们最终的答案啦！

就像小猫咪检查房间里的每一个纸箱，总能找到最舒服的那个！这种方法虽然朴素，但对于这道题来说，又简单又有效，绝对不会出错的喵~ ฅ'ω'ฅ

题解 (代码分析)

好啦，理论说完了，我们来看看代码是怎么实现的吧~

#include <iostream>

// 这个函数解决一个测试用例
void solve() {
    int n;
    std::cin >> n; // 先把 n 读进来喵

    long long max_sum = -1; // 用来记录最大和，初始化成一个很小的值
    int best_x = -1;      // 用来记录产生最大和的 x

    // 从 2 到 n，暴力枚举所有可能的 x
    for (int x = 2; x <= n; ++x) {
        // 对于当前的 x，计算它的倍数和
        long long current_sum = 0;
        
        // 这个循环就是把 x, 2x, 3x... 都加起来
        // multiple 从 x 开始，每次增加 x，直到超过 n
        for (int multiple = x; multiple <= n; multiple += x) {
            current_sum += multiple;
        }

        // 如果当前 x 算出来的和比我们之前记录的最大和还要大
        if (current_sum > max_sum) {
            max_sum = current_sum; // 那就更新最大和
            best_x = x;            // 并且记下这个更棒的 x！
        }
    }

    // 所有 x 都检查完啦，输出最好的那个~
    std::cout << best_x << std::endl;
}

int main() {
    // 这两行是加速输入输出的魔法哦~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); 

    int t;
    std::cin >> t; // 读入测试用例的数量
    while (t--) {
        solve(); // 每个测试用例都解决一遍
    }

    return 0;
}

代码的逻辑和我们刚才分析的一模一样，对吧？一个外层循环枚举 x，一个内层循环累加 x 的倍数，然后一个 if 语句来打擂台，选出最强的 x。非常直观好懂的说！

知识点介绍

这道题虽然简单，但里面也藏着一些有用的知识点哦，学会了对以后更有挑战的题目也有帮助哒！

1. 暴力枚举 (Brute-Force)

暴力枚举，也叫穷举，就是指把所有可能性都一一列举出来，然后逐个判断是否符合条件。就像这道题，我们把 x 从 2 到 n 的所有可能都试了一遍。这种方法的优点是思路简单，容易实现。缺点是当数据范围很大时，它会跑得非常慢（会超时哦！）。所以，使用暴力枚举前，一定要先看看题目给的数据范围，像这道题的 n <= 100 就是一个非常明显的信号啦。

2. 等差数列求和 (Arithmetic Series)

在计算 x 的倍数和时，代码里用了一个循环累加。其实，我们也可以用数学公式来让它变得更快一点点！

x 的倍数是 x, 2x, 3x, ..., kx，其中 k 是最大的整数使得 kx <= n。这个 k 其实就是 n / x 做整除运算的结果。

这个数列的和是：x + 2x + ... + kx = x * (1 + 2 + ... + k)

而 1 + 2 + ... + k 是一个经典的等差数列，它的和是 k * (k + 1) / 2。

所以，总和 Sum = x * k * (k + 1) / 2，其中 k = n / x。

用这个公式，我们就可以把内层循环替换成一行计算，对于更大的 n 会更高效哦！

// 另一种计算 current_sum 的方法
int k = n / x; // 计算 n 是 x 的多少倍
long long current_sum = (long long)x * k * (k + 1) / 2;

是不是很酷喵？数学也是我们强大的武器之一！

---

好啦，这道题的讲解就到这里啦~ 希望主人能够明白！总结一下，就是看到小数据范围，不要害怕，大胆地去尝试暴力枚举，有时候最简单的方法就是最好的方法！喵~ 祝主人刷题愉快，我们下次再见啦！💖