# 题意

题目链接

输入 $t$ 表示 $n$ 的数量，输入 $t$ 个整数 $n$ 。
对于每个 $n$ ，将 $n$ 的每一位拆出来组成一个序列。记该序列为 $N$ 。
对 $N$ 进行全排列，输出 $N$ 的某个排列按照顺序组成的数是素数的排列的数量。

# 举例

比如 $n=123$ ，则 $N=\{1,2,3\}$ 。
那么 $N$ 的全排列是：

$\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}$

上面的每个序列按照顺序组成的数是：

$123,132,213,231,312,321$

上面的数中没有数是素数，那么就输出 $0$ 。

# 分析

本题有两个重要步骤：

生成全排列
判断是否是素数

# 步骤 1

用 DFS 的方式枚举每一种排列。

设当前在求解 $[l,r]$ 区间的元素的全排列。
如果 $l=r$ ，则意味着当前已经生成了一次排列，可以开始判断是否是素数了，
否则遍历当前区间的每一个元素，
将当前遍历到的元素放到当前区间的首位，即第 $l$ 位，
递归求解 $[l+1,r]$ ；
求解后回溯，将当前区间的第 $1$ 个元素，即第 $l$ 个元素放回原位。
然后…… 妥妥的
TLE

用递归的方式求解全排列时间复杂度过高，于是我们可以用 STL 库中的 next_permutation 来生成全排列。

具体细节请看代码。

# 步骤 2

可以用线性筛的方法先筛出来有哪些数是质数。

考虑对于任意一个大于 $1$ 的正整数 $n$ ，那么它的 $x$ 倍就是合数（ $x > 1$ ）。
如果我们从小到大遍历每个数，把当前的数的所有比自己大的倍数标记为合数，那么遍历完成后没有被标记的数就是素数了。
这就是埃氏筛法，时间复杂度 $O(n\log\log n)$ 。

埃氏筛法会将一个合数多次标记，如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 $O(n)$ 了，这就是线性筛。
具体步骤请看代码。

（以上内容改编自 OI-Wiki）

# 代码

	#include <algorithm>
	#include <cstring>
	#include <iostream>
	#include <string>

	// 调试时用来输出日志的，请忽略
	//#define DEBUG

	using std::next_permutation, std::sort, std::swap;
	using std::cin, std::cout, std::endl;
	using std::string;

	const int N = 10000000;

	int t, n;

	// 用来存放 n 的每一位
	int nArray[11];
	// 用来存放 n 的数位个数
	int nArrayLength;

	// 是否是素数的 bool 数组
	bool isPrime[N + 1];
	// 素数的个数
	int primeCount;
	// 记录素数
	int prime[N + 1];

	//// 用于全排列时去除重复元素
	// bool isAPermNArray[N + 1];

	// 记录答案
	int answer;

	// 调试时用来输出日志的，请忽略
	void log ( string logString ) {
	#ifdef DEBUG
	cout << logString;
	#endif
	}

	// 调试时用来输出日志的，请忽略
	void logln ( string logString ) {
	#ifdef DEBUG
	cout << logString << '\n';
	#endif
	}

	// 用线性筛法筛出素数，以初始化 isPrime 数组
	void initIsPrime ( ) {
	memset ( isPrime, true, sizeof isPrime );
	// 0 和 1 不是素数
	isPrime[ 0 ] = false;
	isPrime[ 1 ] = false;
	for ( int i = 2; i <= N; ++ i ) {
	// 如果当前遍历到的数是素数
	if ( isPrime[ i ] ) {
	// 记录
	++ primeCount;
	prime[ primeCount ] = i;
	}
	// 此处详见：
	// https://www.jianshu.com/p/f16d318efe9b
	for ( int j = 1; j <= primeCount && i * prime[ j ] <= N; ++ j ) {
	isPrime[ i * prime[ j ] ] = false;
	if ( i % prime[ j ] == 0 ) {
	break;
	}
	}
	}
	}

	// 用递归枚举全排列会超时
	//
	//// 遍历当前求解的全排列区间的每个元素，
	//// 将遍历到的元素提到当前区间的首位，
	//// 剩下的元素组成的区间递归求解全排列
	// void permNArray ( int l, int r ) {
	// // 当前区间只有一个元素，
	// // 意味着到达递归边界
	// if ( l == r ) {
	// // 将当前的 nArray 存放到 int 变量中，用以判断当前排列是否为素数
	// int nNow = 0;
	// // 有前导 0
	// if ( nArray[ 1 ] == 0 ) {
	// return;
	// }
	// for ( int i = 1; i <= nArrayLength; ++ i ) {
	// nNow = nNow * 10 + nArray[ i ];
	// }
	// // 不是之前出现过的排列，并且是素数
	// if ( ( ! isAPermNArray[ nNow ] ) && isPrime[ nNow ] ) {
	// // 记录答案
	// ++ answer;
	// }
	// isAPermNArray[ nNow ] = true;
	// }
	// else {
	// for ( int i = l; i <= r; ++ i ) {
	// // 将第 i 个元素提到首位
	// swap ( nArray[ l ], nArray[ i ] );
	// // 对剩下的元素组成的区间递归求解其全排列
	// permNArray ( l + 1, r );
	// // 回溯，将刚才提到首位的元素放回原处
	// swap ( nArray[ l ], nArray[ i ] );
	// }
	// }
	// }

	int main ( ) {
	std::ios::sync_with_stdio ( false );
	cin.tie ( 0 );
	cout.tie ( 0 );
	initIsPrime ( );
	cin >> t;
	for ( int tLoop = 1; tLoop <= t; ++ tLoop ) {
	cin >> n;
	// 不要忘记初始化
	memset ( nArray, 0, sizeof nArray );
	nArrayLength = 0;
	// for ( int i = 1; i <= n; ++ i ) {
	// isAPermNArray[ i ] = false;
	// }
	answer = 0;
	// 提取出 n 的每一位放到 nArray 数组
	for ( int i = 1; i <= 10; ++ i ) {
	if ( n <= 0 ) {
	break;
	}
	else {
	nArray[ i ] = n % 10;
	++ nArrayLength;
	n /= 10;
	}
	}
	// 一定要排序，不然无法枚举到所有的排列
	sort ( nArray + 1, nArray + nArrayLength + 1 );
	do {
	// 将当前的 nArray 存放到 int 变量中，用以判断当前排列是否为素数
	int nNow = 0;
	// 有前导 0
	if ( nArray[ 1 ] == 0 ) {
	continue;
	}
	for ( int i = 1; i <= nArrayLength; ++ i ) {
	nNow = nNow * 10 + nArray[ i ];
	}
	if ( isPrime[ nNow ] ) {
	++ answer;
	}
	}
	//next_permutation 会生成序列的所有不同排列，并在枚举完所有排列后返回 false
	while ( next_permutation ( nArray + 1, nArray + nArrayLength + 1 ) );
	cout << answer << '\n';
	}
	cout << endl;
	return 0;
	}

AC 记录

计算机算法竞赛