SP8591 PRIMPERM - Prime Permutations 题解

题目链接

题目大意

给出 \(1\) 个数 \(n\)，求 \(n\) 的各位拆分后重新排列组合得到新数是质数的个数。

思路（欧拉筛，全排列）

对于求质数，与其每组数据运行 \(1\) 次质数筛，不如在一开始就筛出 \([1,10^7]\) 内的所有质数，用 bool 数组统计起来，这样只需运行 \(1\) 次质数筛，大大节约了时间。

对于筛法，这里使用时间复杂度为 \(O(n)\) 的线性筛（欧拉筛），模板如下：

inline void ola(int n){//欧拉筛 
	isprime[1]=false;//1不是质数 
    for(int i=2;i<=n;i++) isprime[i]=true;//默认都是质数 
    for(int i=2;i<=n;i++){//从2开始筛 
        if(isprime[i]) p[++t]=i;//是质数 
        for(int j=1;j<=t&&i*p[j]<=n;j++){
            isprime[p[j]*i]=false;//如果这个数是质数，那么它的倍数肯定不是质数 
            if(i%p[j]==0) break;
        }
    }
}

接下来，我们可以分解 \(n\) 的每一位，用数组存起来，使用 next_permutation 进行全排列，最后得出新数判断即可，时间复杂度 \(O(t (\log_{10} n)!)\)。

注意：

1. 有多组数据。

2. 排列组成的第一个数不能为 \(0\)。

参考代码（请勿抄袭）：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+10;
bool isprime[MAXN];
int p[MAXN],t,n,s[10];
inline void ola(int n){//欧拉筛 
	isprime[1]=false;//1不是质数 
    for(int i=2;i<=n;i++) isprime[i]=true;//默认都是质数 
    for(int i=2;i<=n;i++){//从2开始筛 
        if(isprime[i]) p[++t]=i;//是质数 
        for(int j=1;j<=t&&i*p[j]<=n;j++){
            isprime[p[j]*i]=false;//如果这个数是质数，那么它的倍数肯定不是质数 
            if(i%p[j]==0) break;
        }
    }
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ola(10000000);//筛出质数 
	cin>>t;
	while(t--){
		cin>>n;
		int tot=0,ans=0;
		while(n){//分解各位 
			s[++tot]=n%10;
			n/=10;
		}
		sort(s+1,s+tot+1);//从小到大排 
		do{
			if(!s[1]) continue;//排列组成的第一个数不能为0
			int QwQ=0;
			for(int i=1;i<=tot;i++){
				QwQ*=10;
				QwQ+=s[i];//得出新数 
			}
			if(isprime[QwQ]) ans++;//如果是质数，答案加1 
		}while(next_permutation(s+1,s+tot+1));
		cout<<ans<<endl;
	}
	return 0;
}