题解 AT1489 【文字列と素数】

前置芝士：

1. 质数判定：除了用$\sqrt{n}$ 的数去除外，它除以6一定余1或者余5.

2. 预处理10的n次幂，1e5以内质数.

3. 字符个数超过5就直接退出.

4. 搜索的时候不需要剪枝，一次搜索成本是$\mathit{O}\mathbf{(}\mathbf{120}\mathbf{)}$,可以通过本题.

具体搜索细节看代码

//注意：本代码在某一个非关键地方隐藏了错误
#include<bits/stdc++.h>
using namespace std;
char a[15],t[15];
long long stra,num,flag,used[200],usednum[14];
long long power[114] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000};
bool num1[100000];
int prime[10000];
bool isprime(long long a){//结合之前的预处理与第一条，速度更快
	if(a==1) return 0;
	if(a==2||a==3) return 1;
	if(a%6!=1&&a%6!=5) return 0;
	for(int i=1;prime[i]&&prime[i]*prime[i]<=a;i++)
	   if(a%prime[i]==0) return 0;
	return 1;   
}
void init(){
	int p=0;
	for(int i=2;i*i<=100000;i++)
	   for(int j=i;i*j<=100000;j++)
	      num1[i*j]=1;   
	for(int i=2;i<=100000;i++) 
		if(!num1[i])
			prime[++p]=i;
}
void dfs(int t){
	if(flag) return;
	if(t==stra){//到了规定长度就判定
		if(isprime(num)) {
			flag++;
			cout<<num<<endl;
		}
		return;
	}
	if(used[a[t]]){//字母用了就直接继承之前的
		num+=used[a[t]]*power[stra-1-t];
		dfs(t+1);
		num-=used[a[t]]*power[stra-1-t];
	}
	else
		for(int i=1;i<=9;i++){//没有用就重新挑选
			if(usednum[i]) continue;
			used[a[t]]=i;
			usednum[i]=1;
			num+=i*power[stra-1-t];
			dfs(t+1);
			num-=i*power[stra-1-t];
	      usednum[i]=0;
	      used[a[t]]=0;
		}
	
}
int main(){
	init();
	cin>>a;
	stra=strlen(a);
	int cnt=0,flg,p=1;
	for(int i=0;i<stra;i++) {
		flg=0;
		for(int j=1;j<=5;j++)
			if(a[i]==t[j]) flg++;
		if(!flg){
			cnt++;
			t[p++]=a[i];
		}
	}
	if(cnt>5) cout<<-1;
	else{
		num=0;dfs(0);
		if(!flag) cout<<-1;
	}
	return 0;
}