NO.19十六届蓝桥杯模拟赛第三期上

1

如果一个数 p 是个质数，同时又是整数 a 的约数，则 p 称为 a 的一个质因数。 请问， 2024 的最大的质因数是多少？ 答：23

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //定义一个整数变量n，并将其初始值设为2024 int n = 2024; //定义一个整数类型的向量f，用于存储n的质因数 vector<int> f; //从2开始遍历到sqrt(n)，因为一个数的质因数不会超过它的平方根 for (int i = 2; i * i <= n; i++) { //如果n能被i整除，说明i是n的一个质因数 while (n % i == 0) { //将n除以i，继续寻找n的其他质因数 n /= i; //将找到的质因数i存入向量f中 f.push_back(i); } } //如果经过上述步骤后，n仍然大于1，说明n本身是一个质数，将其存入向量f中 if (n > 1) { f.push_back(n); } //对向量f进行升序排序 sort(f.begin(), f.end()); //将最大质因数输出到标准输出，并换行。 cout << f.back() << '\n'; //表示程序正常结束 return 0; } #include <bits/stdc++.h>：这是一个非标准的头文件，它包含了几乎所有标准库的头文件，使用它可以避免分别包含多个头文件。using namespace std;：使用标准命名空间，这样在代码中就可以直接使用标准库中的类和函数，而无需加上 std:: 前缀。ios::sync_with_stdio(false);：关闭 C++ 标准输入输出流与 C 标准输入输出流的同步，这样可以提高输入输出的效率。cin.tie(nullptr);：解除 cin 和 cout 的绑定，进一步提高输入输出的效率。sort 是 C++ 标准库提供的一个强大的排序工具，在默认情况下它会按照升序对指定范围内的元素进行排序。f.begin()：这是向量 f 的起始迭代器，它指向向量的第一个元素。迭代器可以理解为一种特殊的指针，用于遍历容器中的元素。f.end()：这是向量 f 的末尾迭代器，它指向向量最后一个元素的下一个位置。 质因数分解的基本原理

质因数分解是将一个合数表示为若干个质数相乘的形式。例如，对于数字 12，它可以分解为2×2×3，其中2和3都是质数。在进行质因数分解时，我们需要从最小的质数2开始，依次检查每个数是否是原数的因数。如果是，则将其作为一个质因数记录下来，并将原数除以这个质因数，得到一个新的数，然后继续对新的数进行分解，直到新的数为1为止

2

对于两个整数a, b，既是a的整数倍又是b的整数倍的数称为a和b的公倍数。公倍数中最小的正整数称为a和b的最小公倍数。 请问，2024和1024的最小公倍数是多少？ 答：259072

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //定义两个整数变量n和m，并分别初始化为2024和1024 int n = 2024, m = 1024; cout << n / __gcd(n, m) * m << '\n'; return 0; } __gcd(n, m)：这是 GCC 编译器提供的一个内置函数，用于计算 n 和 m 的最大公约数。在其他编译器中，也可以使用 <numeric> 头文件中的 std::gcd 函数来实现相同的功能。n / __gcd(n, m) * m：根据最大公约数和最小公倍数的关系： L C M ( n , m ) = n × m G C D ( n , m ) LCM(n,m)=\frac{n \times m}{GCD(n,m)} LCM(n,m)=GCD(n,m)n×m​ 这里先将 n 除以 GCD(n, m)，再乘以 m，可以避免在计算  时可能出现的整数溢出问题。 #include <iostream> #include <numeric> int main() { int n = 2024, m = 1024; std::cout << n / std::gcd(n, m) * m << '\n'; return 0; } gcd最大公约数和 lcm最小公倍数

最大公约数GCD 最大公约数指的是两个或多个整数共有约数中最大的一个。

最小公倍数LCM 最小公倍数是指两个或多个整数公有的倍数中最小的一个。

3

如果一个数 p 是个质数，同时又是整数 a 的约数，则 p 称为 a 的一个质因数。 请问， 2024 的所有质因数的和是多少？ 答：40

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n = 2024; vector<int> f; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; f.push_back(i); } } if (n > 1) { f.push_back(n); } sort(f.begin(), f.end()); //定义一个整数变量sum，用于存储质因数的和，初始值为0 int sum = 0; //使用范围for循环遍历向量f中的每个元素 for (auto x : f) { //将每个质因数累加到sum中 sum += x; } cout << sum << '\n'; return 0; } 范围for for (declaration : range) { // 循环体 } declaration：用于声明一个变量，该变量将在每次循环迭代时依次绑定到 range 中的每个元素。range：表示要遍历的对象，可以是数组、容器、初始化列表等可迭代对象。循环体：每次迭代时执行的代码块。 4

请问，在不超过 2024 的数中，最大的质数是多少？ 答：2017

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //递减循环，从2024开始，每次循环将i的值减1，直到找到质数为止 for (int i = 2024;; i--) { //布尔变量flg，初始值为true，用于标记当前的i是否为质数 bool flg = true; //将i的值赋给临时变量t，避免在后续的判断过程中修改i的值 int t = i; //从2开始遍历到，因为一个数的因数不会超过它的平方根 for (int j = 2; j * j <= t; j++) { //如果t能被j整除，说明t不是质数，将flg置为false，并使用break语句跳出内层循环 if (t % j == 0) { flg = false; break; } } //如果flg仍然为true，说明i是质数，将其输出到标准输出，并使用break语句跳出外层循环，结束程序 if (flg) { cout << i << '\n'; break; } } return 0; } 5

如果两个整数 a, b 除了 1 以外，没有其它的公约数，则称整数 a 与 b 互质。 请问，与 2024 互质的数中（包括1），第 2024 小的数是多少？ 答：4655

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n = 2024; //定义一个整数变量cnt，用于记录与n互质的数的个数，初始值为0 int cnt = 0; //这是一个无限循环，从1开始逐个检查整数i for (int i = 1;; i++) { //使用__gcd函数计算i和n的最大公约数，如果最大公约数为1，则说明i和n互质 if (__gcd(i, n) == 1) { //如果i与n互质，则将计数器cnt加1 if (++cnt == 2024) { //当cnt达到2024，找到了第2024个与n互质的数，将其输出并使用break语句跳出循环 cout << i << '\n'; break; } } } return 0; } 6

对于字符串 S=ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN ，请找到S的一个长度不超过10的子串 A，使得（A的长度）乘以（A在S中出现的次数）最大。 请问这个子串是什么？（如果有多个满足条件的，请回答字典序最小的）。 答：NQN

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //定义一个字符串s，并初始化为给定的字符串 string s = "ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN"; //获取字符串s的长度 int n = s.size(); //用于存储最终结果的子串，初始为空 string ans; //用于存储最大的长度乘以出现次数的乘积，初始值为0 int mx = 0; //外层循环枚举子串的长度，从1到10 for (int len = 1; len <= 10; len++) { //内层循环枚举子串的起始位置，确保子串不会超出原字符串的范围 for (int i = 0; i + len - 1 < n; i++) { //使用substr函数提取从位置i开始、长度为len的子串 string subs = s.substr(i, len); //用于记录子串subs在原字符串中出现的次数，初始值为0 int cnt = 0; //遍历原字符串，检查每个长度为len的子串是否与subs相等 for (int j = 0; j + len - 1 < n; j++) { //如果相等，则将计数器cnt加1 if (s.substr(j, len) == subs) { cnt += 1; } } //如果当前子串的长度乘以出现次数的乘积大于之前记录的最大乘积，则更新最大乘积mx和结果子串ans if (len * cnt > mx) { mx = len * cnt; ans = subs; //如果乘积相等，但当前子串的字典序更小，则更新结果子串ans。 } else if (len * cnt == mx && subs < ans) { ans = subs; } } } cout << ans << '\n'; return 0; } for (int i = 0; i + len - 1 < n; i++) 初始化：int i = 0，定义一个整型变量 i 并将其初始值设为 0。i 表示子串在原字符串中的起始位置。循环条件：i + len - 1 < n，这是决定循环是否继续执行的条件。len 是当前正在考虑的子串的长度，n 是原字符串的长度。i + len - 1 表示子串的结束位置（因为数组下标从 0 开始）。这个条件确保子串不会超出原字符串的范围。迭代语句：i++，每次循环结束后，将 i 的值加 1，这样就可以依次尝试原字符串中不同位置作为子串的起始位置。 7

如果一个字符串中只包含字符0和字符1，则称为一个01串（包含全为0的串和全为1的串）。 请问有多少个长度为24的01串，满足任意5个连续的位置中不超过3个位置的值为1。

---

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //定义一个整数变量n，并将其初始值设为24 int n = 24; //使用位运算'1 << 24'计算的值，并将其输出到标准输出，然后换行 cout << (1 << 24) << '\n'; //定义一个整数变量ans，用于记录满足条件的二进制序列的数量，初始值为0 int ans = 0; //使用位运算'1 << n'计算2^n的值，该循环会遍历从0到2^n-1的所有整数，每个整数可以看作一个长度为n的二进制序列 for (int i = 0; i < 1 << n; i++) { //定义一个长度为2的数组cnt，用于统计0和1的个数，初始值都为0 int cnt[2] {}; //遍历二进制序列的前5位 for (int j = 0; j < 5; j++) { // 0 .. 4 //使用位运算`i >> j & 1`提取二进制序列中第`j`位的值（0 或 1），并将对应的计数器加1 cnt[i >> j & 1] += 1; } //如果前5位中1的个数超过3个，则跳过当前二进制序列，继续检查下一个序列 if (cnt[1] > 3) { continue; } //定义一个布尔变量ok，用于标记当前二进制序列是否满足条件，初始值为true bool ok = true; //从第5位开始，依次检查后续连续5位中1的个数 for (int j = 5; j < n; j++) { //移除当前连续5位中最左边的一位，并将对应的计数器减1 cnt[i >> (j - 5) & 1] -= 1; //添加当前连续5位中最右边的一位，并将对应的计数器加1 cnt[i >> j & 1] += 1; //如果当前连续5位中1的个数超过3个，则将ok设为false，并跳出循环 if (cnt[1] > 3) { ok = false; break; } } //如果ok为false，说明当前序列不满足条件，跳过该序列，继续检查下一个序列 if (!ok) { continue; //如果ok为true，说明当前二进制序列满足条件，将ans加1 } else { ans += 1; } } cout << ans << '\n'; return 0; }

1 << 24 位运算就是直接对整数的二进制位进行操作。<< 是左移运算符，它会将一个数的二进制表示向左移动指定的位数。 数字 1 的二进制表示是 0000 0000 0000 0000 0000 0000 0000 0001 移动后的二进制结果是 0001 0000 0000 0000 0000 0000 0000 0000

i >> j 是 C++ 中的右移运算符表达式 右移运算符：>> 是右移运算符，用于将一个整数的二进制表示向右移动指定的位数 对于表达式 i >> j，它会把整数 i 的二进制形式向右移动 j 位。

& 1 通常用于提取一个整数二进制表示的最低位（即最右边的一位）。因为数字 1 的二进制表示在不同位数系统下，都是除了最低位为 1 其余位为 0 当一个整数与 1 进行按位与操作时，其他位都会因为和 0 进行按位与而变为 0，只有最低位会根据其自身的值（0 或 1）决定结果。如果最低位是 0，那么结果就是 0；如果最低位是 1，那么结果就是 1。