yukicoder : No.774 tatyamと素数大富豪

Easyまではいいけども…。
https://yukicoder.me/problems/no/774

問題

N個の正整数が与えられる。
これらを並べ替えて連結して得られる数値のうち、素数の中で最大値を求めよ。

解法

並べ方はまぁ適当に総当たりしよう。
桁数が多いので、素数判定はミラーラビン検定しよう。

int N;
int A[10];
ll ret=-1;
vector<ll> V;
bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return (v!=1);
}

// ミラーラビン
ll modpow(__int128_t a, ll n, ll mo) {
	__int128_t r=1;
	a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
bool MillerRabin(ll v,int loop=10) {
	ll d=v-1;
	int s=0,i,j;
	if(v<=1) return false;
	if(v==2) return true;
	if(v%2==0) return false;
	while(d%2==0) d/=2,s++;
	
	FOR(i,loop) {
		ll a=abs(1LL*rand()*rand()+rand())%(v-2)+1;
		ll r=modpow(a,d,v);
		if(r==1 || r==v-1) continue;
		FOR(j,s) {
			r=modpow(r,2,v);
			if(r==v-1) break;
		}
		if(j==s) return false;
	}
	return true;
}

void dfs(ll cur,int mask) {
	if(mask==(1<<N)-1) V.push_back(cur);
	
	int i;
	FOR(i,N) if((mask&(1<<i))==0) {
		ll ne;
		if(A[i]>=10) ne=cur*100+A[i];
		else ne=cur*10+A[i];
		dfs(ne,mask|(1<<i));
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	int ma=-1;
	dfs(0,0);
	srand(time(NULL));
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	reverse(ALL(V));
	FORR(v,V) {
		if(MillerRabin(v,30)) {
		cout<<v<<endl;
		return;
		}
	}
	
	cout<<-1<<endl;
}

まとめ

ミラーラビンを★2.5というと、ちょっとつらいかも？
でも１回作っておけばライブラリゲーになっちゃうので、難易度づけ難しいね。