R0012. 「T2」回文质数 Solution

返回题目

简要题意：

给定一个区间的左边界和右边界，输出其中所有既是回文数也是质数的数。

题目分析：

先思考做法：

1. 暴力枚举 $[l,r]$ 的每一个数。

数据范围 $1$ 的后面有 $8$ 个 $0$ 啊，好好想想你在做什么。

2. 因为判断回文数较快且回文数较少，所以先判断回文数，再判断质数。

看起来比较合理了吧，但是复杂度 $\mathcal{O}(\sum_{i=l}^{r} \dfrac{i}{2}+\sqrt{i})$，或者说简单点：$\mathrm{TLE}$。

所以我们采用更快的方法，生成回文质数：

int reverse(int n) {
	int a[10], i, sum = 0, t = n;
	for (i = 0; n > 0; i++, n /= 10) {
		a[i] = n % 10;
	}
	for (int j = 1; j < i; j++) {
		sum = sum * 10 + a[j];
	}
	return sum + t * pow(10, i - 1);
}

bool prime(int n) {
	if (n == 1) {
		return false;
	}
	if (n == 2) {
		return true;
	}
	if (n % 3 == 0) {
		return false;
	}
	for (int i = 7; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}
void dfs(int i) {
	int x = reverse(i);
	if (x > r) {
		return;
	}
	if (prime(x) && x != 7 && x >= l) {
		a[sum++] = x;
	}
	for (int j = 0; j < 10; j++) {
		if (i * i < r) {
			dfs(i * 10 + j);
		} else {
			return;
		}
	}
}

但是，你会惊讶的发现，这么写是会 $\mathrm{WA}$ 滴！

因为它是无序生成的，所以要排序，这里用的是二分快排：

void qsort(int l, int r) {
	int i = l, j = r, mid = a[(l + r) / 2];
	while (i <= j) {
		while (a[i] < mid)
			i++;
		while (a[j] > mid)
			j--;
		if (i <= j)
			swap(a[i++], a[j--]);
	}
	if (i < r)
		qsort(i, r);
	if (l < j)
		qsort(l, j);
}

注意 $5,7,11$ 小于 $3$ 位，需要特判。

$\mathrm{Code:}$

#include <bits/stdc++.h>
using namespace std;
int l, r, sum, a[1000000];

int reverse(int n) {
	int a[10], i, sum = 0, t = n;
	for (i = 0; n > 0; i++, n /= 10) {
		a[i] = n % 10;
	}
	for (int j = 1; j < i; j++) {
		sum = sum * 10 + a[j];
	}
	return sum + t * pow(10, i - 1);
}

bool prime(int n) {
	if (n == 1) {
		return false;
	}
	if (n == 2) {
		return true;
	}
	if (n % 3 == 0) {
		return false;
	}
	for (int i = 7; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

void qsort(int l, int r) {
	int i = l, j = r, mid = a[(l + r) / 2];
	while (i <= j) {
		while (a[i] < mid)
			i++;
		while (a[j] > mid)
			j--;
		if (i <= j)
			swap(a[i++], a[j--]);
	}
	if (i < r)
		qsort(i, r);
	if (l < j)
		qsort(l, j);
}

void dfs(int i) {
	int x = reverse(i);
	if (x > r) {
		return;
	}
	if (prime(x) && x != 7 && x >= l) {
		a[sum++] = x;
	}
	for (int j = 0; j < 10; j++) {
		if (i * i < r) {
			dfs(i * 10 + j);
		} else {
			return;
		}
	}
}

int main() {
	cin >> l >> r;
	if (l == 5) {
		a[0] = 5;
		a[1] = 7;
		a[2] = 11;
		sum = 3;
	} else if (l <= 7) {
		a[0] = 7;
		a[1] = 11;
		sum = 2;
	} else if (l <= 11) {
		a[sum++] = 11;
	}
	dfs(1);
	dfs(3);
	dfs(7);
	dfs(9);
	qsort(0, sum - 1);
	for (int i = 0; i < sum; i++) {
		cout << a[i] << '\n';
	}
	return 0;
}

即可 $\mathrm{AC}$。