自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:15:15，当前版本为作者最后更新于2023-08-12 10:44:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 8 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定 $n$ 和 $a _ 1, a _ 2, \cdots, a _ n$。当 $a$ 序列中某两个元素相乘后是 $147$ 或 $154$ 的倍数，所有 $a _ i$ 变为原来的两倍。求能否通过若干次（或 $0$ 次）相乘，使得 $a _ 1 + a _ 2 + \cdots + a _ n \geq k$。

题目分析

本题考察较复杂的模拟。

不难发现这样几条性质：

1. 单个元素（$n = 1$）一定无法反应。
2. 如果两个元素 $a _ i, a _ j$ 可以反应，那么它们就可以一直反应，使得序列无限翻倍。
3. $a _ i \leq 10 ^ 9$，那么 $a _ 1 + a _ 2 + \cdots + a _ n$ 不会超过 $10 ^ 9 \times 10 ^ 6 = 10 ^ {15}$。那么，当 $k > 10 ^ {15}$ 时，如果元素无法反应，那么一定无法达到目的。
4. $k$ 的位数 $\geq 17$ 时，$k \geq 10 ^ {16}$，而 $10 ^ {16}$ 可以被 long long 容纳下。
5. $154 = 2 \times 7 \times 11$。如果两个元素 $a _ i, a _ j$ 乘积为 $154$ 的倍数，且这两个元素均不是 $154$ 的倍数，那么其中一个元素一定是 $2 \times 7 = 14$ 或 $2 \times 11 = 22$ 或 $7 \times 11 = 77$ 的倍数，而另一个元素需要对应的是 $11$ 或 $7$ 或 $2$ 的倍数。
6. $147 = 3 \times 7 \times 7$。如果两个元素 $a _ i, a _ j$ 乘积为 $147$ 的倍数，且这两个元素均不是 $147$ 的倍数，那么其中一个元素一定是 $3 \times 7 = 21$ 或 $7 \times 7 = 49$ 的倍数，而另一个元素需要对应的是 $7$ 或 $3$ 的倍数。

因此，对于每组数据，我们可以按照以下步骤处理：

$k$ 的处理

由性质 3 和性质 4，我们使用字符串 std::string 或 char[] 读入 $k$。读入后，首先判断 $k$ 的长度是否 $\geq 17$。如果是，我们直接将整数类型的 $k$ 设为 $10 ^ {16}$；否则，我们手动模拟/使用库函数，将字符串类型的 $k$ 转换为整数类型。

C++ 的 std::stoll() 可以将 std::string 转换为 long long 类型，这里使用这种方法进行转换。

string s;
cin >> s;
if (s.length() < 17) {
    k = stoll(s);
} else {
    k = 1e16;
}

对 $n = 1$ 的特殊处理

对于 $n = 1$，由于单个元素无法反应（性质 1），因此只需要判断仅有的一个元素 $a _ 1$ 和 $k$ 的大小关系。

if (n == 1) {
    if (a[1] >= k) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    continue;
}

直接判断当前元素是否总和 $\geq k$

我们只需读入时将所有元素相加，并与处理后的整数 $k$ 作比较，即可得到一个初步判断。

找到可能反应的元素

由性质 5 和性质 6，我们可以遍历一次数组，找到能够整除 $14, 22, 77, 21, 49$ 的元素。但是，对于另一个元素，如果我们再进行同样的遍历，时间复杂度为 $O(n ^ 2)$，不能接受。

所以我们考虑分别记录能够整除 $2, 3, 7, 11$ 的元素的数量。

int cnt[15];
int ops[] = { 2, 3, 7, 11 };
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) {
    for (int j = 0 ; j < 4; ++j) {
        if (a[i] % ops[j] == 0) {
            ++cnt[ops[j]];
        }
    }
}

首先我们可以扫描查找是否有直接为 $147$ 或 $154$ 的倍数的元素，如果有则直接输出 Yes，进行下一组数据的运算。

如果没有，接下来，遍历数组查找能够整除 $14, 22, 77, 21, 49$ 的元素，并分别判断有多少能够整除 $11, 7, 2, 7, 3$ 的元素。对于 $14, 22, 77, 49$，只要有一个对应的另一个元素即可；但是对于 $21$，由于 $21$ 本身可以整除 $7$，因此需要有至少两个对应的元素。

int flag = 0;
for (int i = 1; i <= n; ++i) {
    if (a[i] % 154 == 0 || a[i] % 147 == 0) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 21 == 0 && cnt[7] >= 2) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 49 == 0 && cnt[3]) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 77 == 0 && cnt[2]) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 14 == 0 && cnt[11]) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 22 == 0 && cnt[7]) { cout << "Yes" << endl; flag = 1; break; }
}
if (!flag)
    cout << "No" << endl;

通过以上步骤，我们就可以完成所有判断。

视频讲解

视频题解后续将会上传。