三、编程题（每题 25 分，共 50 分）
1、因数分解
问题描述
每个正整数都可以分解成素数的乘积，例如：6= 2×3、20=2² × 5 。

现在，给定⼀个正整数 N ，请按要求输出它的因数分解式2 ≤ N ≤ 10¹² 。
输入描述
输⼊第⼀⾏，包含⼀个正整数 。约定
输出描述
输出⼀⾏，为 N 的因数分解式。要求按质因数由⼩到⼤排列，乘号⽤星号*表⽰，且左右各空⼀格。当且仅当⼀个素数出现多次时，将它们合并为指数形式，⽤上箭头^表⽰，且左右不空格。
样例输入 1

6

样例输出 1

2*3

样例输入 2

20

样例输出 2

2^2*5

样例输入 3

23

样例输出 3

23

【题目大意】输入一个正整数 N，按格式输出它的因数分解式。

【考纲知识点】初等数论，多重循环，算术运算
【解题思路】
每个正整数 N 的质因数分解形式是唯一的。可以设计一个简单的算法，在2~N范围内按从 小到大的顺序枚举每一个整数，如果该整数能整除N，则把该整数就是 N 的一个 质因数，将它从 N 中分解出去，循环执行直到N 不能被分解为止。再分解过程中按题目要求输出因数分解式。
【参考程序】

#include <iostream>
using namespace std;
int main(){
	long long N=0;
	cin >>N;
	bool first = true;
	for(long long p=2;p*p<=N;p++){
		if(N%p!=0) continue;
		int cnt=0;
		while(N%p==0){
			cnt++;
			N /= p;
		}
		if(first){
			first = false;
		}else{
			cout <<"*";
		}
		cout<< p;
		if(cnt >1)
			cout <<"^" << cnt;
	}
	if(N>1){
		if(first){
			first = false;
		} else {
			cout<<"*";
		}
		cout << N;
	}
	cout << endl;
	return 0 ;
}

2、巧夺大奖
问题描述
⼩明参加了⼀个巧夺⼤奖的游戏节⽬。主持⼈宣布了游戏规则：

(1) 游戏分为 n 个时间段，参加者每个时间段可以选择⼀个⼩游戏。

(2) 游戏中共有 n 个⼩游戏可供选择。
(3) 每个⼩游戏有规定的时限和奖励。对于第 n 个⼩游戏，参加者必须在第Ti 个时间段结束前完成才能得到奖励 R _i 。
⼩明发现，这些⼩游戏都很简单，不管选择哪个⼩游戏，他都能在⼀个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个⼩游戏，才能使得总奖励最⾼？
输入描述
输入第一行，包含一个正整数 n 。n 既是游戏时间段的个数，也是小游戏的个数。约定 1 ≤ n ≤ 500。
输入第二行，包含 n 个正整数。第 i 个正整数为 T _i ，即第个小游戏的完成期限。约定 1 ≤ T _i ≤ n 。
输入第三行，包含 n 个正整数。第 i 个正整数为 R _i ，即第i 个小游戏的完成奖励。约定 1 ≤ R _i ≤ 1000。
输出描述
输出一行，包含一个正整数 C，为最高可获得的奖励。

样例输入 1

7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

样例输出 1

230

样例解释 1
7 个时间段可分别安排完成第 4、2、3、1、6、7、5 个小游戏，其中第4、2、3、1、7 个小游戏在期限内完成。因此，可以获得总计 40+60+50+70+10=230 的奖励。

【题目大意】在 n 个时间段内完成 n 个小游戏，每个小游戏完成的时间和获得奖励不同，如何选择小游戏使得最后获得奖励最高。
需要注意这句话的理解“对于第 i 个⼩游戏，参加者必须在第Ti 个时间段结束前完成才能得到奖励”，也就是在第 1~Ti 个时间段范围之内，其中任意一个时间段都可以完成第 i 个游戏。
【考纲知识点】贪心算法、数组、sort 函数。
【解题思路】
本题采用贪心策略，想要获得的最高奖励，优先完成获得奖励多的游戏，同时考虑在完成第 i 个游戏的时候，第 1~Ti 个时间段是否被占用，如果都被占用，那么该游戏就不能被完成。解题步骤如下：
1) 首先创建结构体 game 用于保存每个游戏的信息，包括游戏时间期限T和对应的奖励 R，并创建 games[505]用于保存 n 个游戏的信息
2) 按题目要求输入数据，并保存在 games 数组中
3) 根据游戏的奖励，对数组 games 进行降序排序，
4) 遍历排序后的数组 games，依次判断第 i 个游戏是否能完成，如果能完成就累加当前游戏的奖励 games[i].R
5) 判断游戏是否能完成可以使用一个数组进行标记，标记第1n 个时间段是否被占用，如果第 i 个游戏的可完成时间段为第 1Ti，如果该范围都被占用，则第i
个游戏无法完成。
【参考程序】

#include <iostream>
#include <algorithm>
using namespace std;
int n=0;
struct game_t{
	int T, R;
}games[500];
bool game_cmp(game_t x,game_t y){
	return x.R>y.R;
}
bool arrange[500];
int main(){
	cin >>n;
	for(int i=0;i<n;i++)
		arrange[i] = false;
	for(int i=0;i<n;i++)
		cin >>games[i].T;
	for(int i=0;i<n;i++)
		cin >>games[i].R;
	sort(games,games+n,game_cmp);
	int sum=0;
	for(int i=0;i<n;i++){
		for(int t=games[i].T-1;t>=0;t--)
			if(!arrange[t]){
				arrange[t]= true;
				sum += games[i].R;
				break ;
			}
		}
	cout<<sum<<endl;
	return 0 ;
}