CF1883C 题解

· · 题解

本文章与博客园同步发布 洛谷传送门 CF传送门

思路

首先， 一眼丁真， 题目中说， 要 \prod \limits_{i=1}^n a_i \bmod k = 0, 即 a_1 至 a_n 中有能够 \bmod k 为零的， 则遍历一遍数组， 答案取 \min \sum \limits_{i=1}^{n} (k - a[i] \bmod k)。

当然， 这是错误的， 当 k 为 4 时， 它还可以变成 k = 2 \times 2， 所以该怎么办呢？

因为 1 \le k \le 5， 所以我们可以特判。令 c = \sum \limits_{i=1}^{n}a_i \bmod 2， 则答案为 \max(0, 2-c)。

思路知道了后， 代码就很简单了， 在此不放。