算法分析与设计第二次作业题题解

题目发布于2021年9月30日上午十点。

Problem A

题目描述

如果一个质数能被表示为三个不同的质数的和的形式，那么我们称它为立方质数。

现在给你一个数\(n(n \leq 1000)\)，判断它是不是立方质数。

题解

观察\(n\)的范围，直接暴力枚举即可。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
bool is_prime(int n) {
	if (!(n % 2)) {
		return false;
	}
	if (n == 1) {
		return false;
	}
	for (int i = 3; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	vector<int> primeList;
	int n;
	cin >> n;
	if (!is_prime(n)) {
		cout << "No" << endl;
		return 0;
	}
	for (int i = 2; i <= n; i++) {
		if (is_prime(i)) {
			primeList.push_back(i);
		}
	}
	int l = primeList.size();
	for (int i = 0; i < l; i++) {
		for (int j = i + 1; j < l; j++) {
			for (int k = j + 1; k < l; k++) {
				if (n == primeList[i] + primeList[j] + primeList[k]) {
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

Problem B

题目描述

有\(n\)盏灯，编号为\(1,2,\dots,n\)，初始灯都是关着的。有\(n\)个人，第\(i\)个人会打开所有编号为\(i\)的倍数的灯，那么最后有几盏灯是亮着的？

题解

实际上，仔细读题发现，最后只有被按了奇数次的灯会亮着，也就是说，本题是求在区间\([1, n]\)中的整数\(i\)满足条件当且仅当\(i\)恰好有奇数个不同的因数。大于\(1\)的任意一个正整数的因数都是成对出现的，除非这个数是完全平方数。说到底，这个题就是要求\([1, n]\)中有多少个完全平方数。直接返回\(\lfloor \sqrt{n} \rfloor\)即可。

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int i;
	for(i = 1; i * i <= n; i++){}
	cout << i - 1 << endl;
	return 0;
}

Problem C

题目描述

小明刚买了一个机械键盘，但他在用机械键盘打字的时候发现键盘的Home键和End键坏掉了，于是他在打字的时候光标有时会突然跑到行首，有时又会突然跑到行尾，现在给你键盘的输入，求最后屏幕上的字符串。

题解

实际上需要费脑筋的是输入多个home的情况。

#include <iostream>
#include <string> 
#define FRONT true
#define BACK false

using namespace std;

int main() {
	string s, fr, ans;
	cin >> s;
	bool mode = BACK;
	for (auto c : s) {
		if (c == '[') {
			mode = FRONT;
			ans = fr + ans;
			fr.clear();
		}
		else if (c == ']') {
			mode = BACK;
		}
		else {
			if (mode == BACK) {
				ans.push_back(c);
			}
			else {
				fr.push_back(c);
			}
		}
	}
	ans = fr + ans;
	cout << ans << endl;
	return 0;
}

Problem D

题目描述

对于数\(7331\)而言，\(7,73,733,7331\)都是质数，因此\(7331\)被称作长度为\(4\)的特殊质数。

输入为\(N(1 \leq N \leq 8)\)，求出所有长度为\(N\)的特殊质数。

题解

实际上可以使用宽搜求解。

#include <iostream>
#include <queue>
int main() {
	int N;
	cin >> N;
	queue<int> ans({2, 3, 5, 7});
	int lastCount = 4;
	int curCount = 0;
	for (int i = 2; i <= N; i++) {
		curCount = 0;
		for (int j = 1; j <= lastCount; j++) {
			int cur = ans.front();
			ans.pop();
			cur *= 10;
			for (int k = 1; k <= 9; k += 2) {
				if (is_prime(cur + k)) {
					ans.push(cur + k);
					curCount++;
				}
			}
		}
		lastCount = curCount;
	}
	while(!ans.empty()) {
		cout << ans.front() << endl;
		ans.pop();
	}
	return 0;
}

Problem E

题目描述

输入一个\(32\)位无符号整数，输出其高\(16\)位与低\(16\)位交换后的结果。

题解

#include <iostream>
#define base 65536 //2^16
using namespace std;
int main(){
	size_t n;
	cin >> n;
	size_t low = n / base, high = n % base;
	cout << high * base + low << endl;
	return 0;
}

Problem F

题目描述

输入两个正整数\(x_0,y_0(2≤x_0≤100000，2≤y_0≤1000000)\)，求出满足下列条件的\(P,Q\)的个数：

（1）\(P,Q\)都是正整数；

（2）要求\(P,Q\)以\(x_0\)为最大公约数，以\(y_0\)为最小公倍数。

试求满足条件的所有可能的两个正整数的个数。

题解

设\(P=k_1x_0, Q=k_2x_0（k_1与k_2互质）\), 则依题意\(k_1k_2x_0=y_0\)，也就是说\(k_1k_2=\displaystyle \frac{y_0}{x_0}\)。若\(x_0\)不能整除\(y_0\)，则满足要求的个数为0；否则只要统计\(\displaystyle \frac{y_0}{x_0}\)的互质因数的组数即可（也就是所有的非平方根因数的个数）。

#include <iostream>
using namespace std;
int gcd(int a, int b) {
	return a % b == 0 ? b : gcd(b, a % b);
}
int main() {
	int x0, y0;
	cin >> x0 >> y0;
	if (y0 % x0) {
		cout << 0 << endl;
		return 0;
	}
	int p = y0 / x0;
	int ans = 0;
	for (int i = 1; i * i < p; i++) {
		if (p % i == 0 && gcd(i, p / i) == 1) {
			ans += 2;
		}
	}
	cout << ans << endl;
	return 0;
}