喵哈喽~！各位主人，欢迎来到我的题解小课堂~ 今天我们要看的是一道可爱的数学题，Codeforces 1883C - Raspberries。别看它叫树莓，其实和树莓一点关系都没有哦，噗嗤~ 让我们一起来看看怎么用最少的力气解决它吧！喵~

题目大意

这道题是这样哒：

我们有一个装着 n 个整数的数组 a，还有一个整数 k（k 的值只会在 2, 3, 4, 5 之间哦）。我们可以进行一种操作：选择数组里的任意一个数 a_i，然后把它变成 a_i + 1。这个操作可以无限次使用。

我们的目标是，通过最少的操作次数，让数组里所有数字的乘积 a_1 * a_2 * ... * a_n 能够被 k 整除。

简单来说，就是用最少的 "+1" 操作，让整个数组的乘积成为 k 的倍数。是不是很简单呀？喵~

题解方法

要让一堆数字的乘积能被 k 整除，其实就是要让这些数字分解质因数后，所有质因子的集合里，包含了 k 的所有质因子。

举个栗子，如果 k = 4，因为 4 = 2 * 2，所以我们需要所有数字的质因子中至少有两个 2。

因为 k 的值非常小（只有 2, 3, 4, 5），我们可以分开讨论，找到最简单的策略！

策略一：改造一个数就搞定！

最直接的想法就是，我们只动一个数字 a_i，让它自己变成 k 的倍数。这样一来，整个数组的乘积自然也就能被 k 整除了，对吧？

那么，要把一个数 a_i 变成 k 的倍数，需要多少次操作呢？ 其实就是把它变成大于等于 a_i 的、最小的那个 k 的倍数。 比如 a_i = 7, k = 5。7 不是 5 的倍数，下一个 5 的倍数是 10。我们需要 10 - 7 = 3 次操作。 如果 a_i = 10, k = 5，它已经是 5 的倍数了，那就不需要操作，0 次！

这个操作次数可以用一个很漂亮的公式来算：(k - a_i % k) % k。

• a_i % k 是 a_i 除以 k 的余数。
• k - (a_i % k) 就是还需要加多少才能凑成 k。
• 最后再 % k 是为了处理 a_i 本身就是 k 的倍数的情况。这时 a_i % k 是 0，k - 0 = k，但我们其实需要 0 次操作，所以 k % k = 0 正好解决了这个问题。

我们可以遍历数组里所有的 a_i，对每个 a_i 都计算这个操作次数，然后取一个最小值。这个就是我们的一个备选答案 ans。

对于 k 是质数（2, 3, 5）的情况，这个策略就是最优的了。因为质数不能再分解，我们必须得凑出一个 k 的倍数来。

策略二：特殊情况 k = 4

当 k = 4 的时候，事情就变得有趣起来了，喵~ 4 = 2 * 2，所以我们需要乘积的质因子中至少有两个 2。 这可以通过两种方式实现：

1. 和上面一样：让某一个 a_i 变成 4 的倍数。这个成本我们已经算过了。
2. 合作的力量：让两个不同的数 a_i 和 a_j 都变成 2 的倍数（也就是偶数）。一个偶数提供一个质因子 2，两个偶数就提供了两个质因子 2，它们的乘积自然就是 4 的倍数啦！

现在我们来计算一下第二种方式的成本： 我们需要凑够两个偶数。我们先数一数数组里本来就有多少个偶数，记作 evens_count。

• 如果 evens_count >= 2，太棒了！我们已经有两个或更多偶数了，什么都不用做，操作次数为 0。
• 如果 evens_count == 1，我们还差一个偶数。找一个奇数，给它 +1，它就变成偶数了。成本是 1。
• 如果 evens_count == 0，我们需要两个偶数。那就找两个奇数，都给它们 +1，成本是 1 + 1 = 2。

所以，对于 k = 4 的情况，最终的答案是 min(策略一的最小操作数, 策略二的最小操作数)。

总结一下

1. 初始化一个 min_ops 为 k（一个比较大的安全值）。
2. 遍历数组中每个数 val：
   • 计算让 val 变成 k 的倍数所需的操作数 (k - val % k) % k，用它来更新 min_ops。
   • 如果 k=4，顺便数一下数组里有多少个偶数 evens_count。
3. 遍历结束后：
   • 如果 k=4，再计算一下凑够两个偶数的操作数 max(0, 2 - evens_count)，然后用它和当前的 min_ops 比较，取更小的一个。
   • 如果 k 是 2, 3, 5，直接输出 min_ops 就好啦。

就是这样，喵~ 是不是很清晰了呢？

题解

这是可以直接运行的 C++ 代码哦，我已经加上了可爱的注释，方便主人理解每一行都在做什么~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 解决单个测试用例的函数喵~
void solve() {
    int n;
    int k;
    std::cin >> n >> k;

    // 喵~ 先假设最坏情况，操作次数最多是k-1次，比如把1变成k。
    // 为了方便，直接设成k也没问题。
    int min_ops = k; 
    
    // 如果k=4，我们需要数一数有多少个偶数，喵呜~
    int evens_count = 0;

    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;

        // 策略一：让一个数变成k的倍数。
        // (k - val % k) % k 这个表达式很巧妙，能直接算出需要加上的值。
        // 如果val已经是k的倍数，val % k = 0, (k-0)%k = 0，正好是0次操作！
        min_ops = std::min(min_ops, (k - val % k) % k);

        // 如果 k 是 4，我们就要特别关注偶数啦。
        if (val % 2 == 0) {
            evens_count++;
        }
    }

    // 策略二：只在 k=4 的时候需要考虑。
    // 目标是让数组里有两个偶数。
    if (k == 4) {
        // 我们需要 2 个偶数，现在已经有 evens_count 个了。
        // 如果 evens_count = 0, 还需要 2 个, 操作 2 次。
        // 如果 evens_count = 1, 还需要 1 个, 操作 1 次。
        // 如果 evens_count >= 2, 还需要 0 个, 操作 0 次。
        // 这个逻辑可以用 max(0, 2 - evens_count) 来概括，真聪明~
        int ops_from_evens = std::max(0, 2 - evens_count);
        
        // 最终答案是两种策略里更优的那个！
        min_ops = std::min(min_ops, ops_from_evens);
    }

    std::cout << min_ops << "\n";
}

int main() {
    // 快速输入输出，让程序跑得像小猫一样快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但里面藏着一些很有用的数学小知识哦！

1. 模运算 (Modular Arithmetic)

   • % 运算符在编程里就是取余数的意思。a % k 得到 a 除以 k 的余数。
   • 这个知识点在本题的核心应用是计算将一个数 val 变为 k 的倍数所需的最少操作数。公式 (k - val % k) % k 是一个非常简洁和优雅的实现。它避免了使用 if-else 来判断 val 是否已经是 k 的倍数，让代码更紧凑。

2. 整除性与质因数分解 (Divisibility and Prime Factorization)

   • 核心思想：一个数 P 能被 k 整除，当且仅当 k 的所有质因子（包括重复的）都在 P 的质因子集合中。
   • 应用到本题：我们的 P 是 a_1 * a_2 * ... * a_n。它的质因子集合是所有 a_i 的质因子集合的并集。
   • k=2, 3, 5 (质数): k 只有一个质因子，就是它本身。所以我们只需要让乘积中出现一个因子 k 就行。最简单的方法就是让某个 a_i 成为 k 的倍数。
   • k=4 (合数): 4 的质因子是 2, 2。我们需要两个因子 2。
     • 可以来源于同一个 a_i（a_i 是 4 的倍数，比如 4, 8, 12...）。
     • 也可以来源于两个不同的 a_i 和 a_j（它俩都是 2 的倍数，也就是偶数）。
     • 这就是为什么 k=4 时需要一个特殊的分支逻辑来比较两种策略的优劣。

理解了这些，下次遇到类似的题目，主人也一定能像我一样，一眼就看穿它的小把戏啦！喵~ 如果还有不懂的地方，随时可以再来问我哦！