欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

编程题

B3871 因数分解

【题目来源】

洛谷：[B3871 GESP202309 五级] 因数分解 - 洛谷

【题目描述】

每个正整数都可以分解成素数的乘积，例如： \(6=2\times 3\)，\(20=2^2\times5\)。

现在，给定一个正整数，请按要求输出它的因数分解式。

【输入】

输入第一行，包含一个正整数 \(N\)。约定 \(2 \le N \le 10^{12}\)。

【输出】

输出一行，为的因数分解式。要求按质因数由小到大排列，乘号用星号 * 表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头 ^ 表示，且左右不空格。

【输入样例】

【输出样例】

2 * 3

【算法标签】

《洛谷 B3871 因数分解》 #数论# #GESP# #2023#

【代码详解】

#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 1005;  // 最大质因子数量
int n;               // 要分解的数
int a[N], b[N];      // a[i]存储第i个质因子，b[i]存储对应的指数
int cur;             // 当前质因子数量signed main()
{// 输入要分解的数cin >> n;// 质因数分解for (int i = 2; i * i <= n; i++)  // 只需检查到√n{if (n % i == 0)  // 如果i是n的因子{a[++cur] = i;  // 记录质因子b[cur] = 0;    // 初始化指数// 计算指数：不断除以i直到不能整除while (n % i == 0){b[cur]++;  // 指数加1n /= i;    // 除以质因子}}}// 处理剩余的部分// 如果n>1，说明n本身是一个质数if (n > 1){a[++cur] = n;  // 剩余的n是质因子b[cur] = 1;    // 指数为1}// 调试输出// for (int i = 1; i <= cur; i++)//     cout << a[i] << ' ' << b[i] << endl;// 格式化输出质因数分解结果for (int i = 1; i < cur; i++)  // 前cur-1个因子{if (b[i] == 1){cout << a[i];  // 指数为1，只输出因子}else{cout << a[i] << "^" << b[i];  // 指数大于1，输出指数形式}cout << " * ";  // 因子间用乘号连接}// 输出最后一个因子（不加乘号）if (b[cur] == 1){cout << a[cur];  // 指数为1}else{cout << a[cur] << "^" << b[cur];  // 指数大于1}return 0;
}

【运行结果】

6
2 * 3

B3872 巧夺大奖

【题目来源】

洛谷：[B3872 GESP202309 五级] 巧夺大奖 - 洛谷

【题目描述】

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：

游戏分为 \(n\) 个时间段，参加者每个时间段可以选择一个小游戏。
游戏中共有 \(n\) 个小游戏可供选择。
每个小游戏有规定的时限和奖励。对于第 \(i\) 个小游戏，参加者必须在第 \(T_i\) 个时间段结束前完成才能得到奖励 \(R_i\)。

小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？

【输入】

输入第一行，包含一个正整数 \(n\)。\(n\) 既是游戏时间段的个数，也是小游戏的个数。约定 \(1\le n\le500\)。

输入第二行，包含 \(n\) 个正整数。第 \(i\) 个正整数为 \(T_i\)，即第 \(i\) 个小游戏的完成期限。约定 \(1\le T_i\le n\)。

输入第三行，包含 \(n\) 个正整数。第 \(i\) 个正整数为 \(R_i\)，即第 \(i\) 个小游戏的完成奖励。约定 \(1\le R_i\le 1000\)。

【输出】

输出一行，包含一个正整数 \(C\)，为最高可获得的奖励。