結果

問題 No.774 tatyamと素数大富豪
ユーザー chocoruskchocorusk
提出日時 2018-12-22 00:42:10
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,195 bytes
コンパイル時間 1,006 ms
コンパイル使用メモリ 100,944 KB
実行使用メモリ 26,012 KB
最終ジャッジ日時 2024-09-25 09:48:34
合計ジャッジ時間 7,458 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 5
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAX=5000000;
vector<ll> prime;
bool isprime[MAX];
void sieve(){
	for(ll i=3; i<MAX; i+=2){
		isprime[i]=1;
	}
	isprime[2]=1;
	prime.push_back(2);
	for(ll i=3; i<MAX; i++){
		if(isprime[i]){
			prime.push_back(i);
			for(ll j=2*i; j<MAX; j+=i){
				isprime[j]=0;
			}
		}
	}
	return;
}
ll mulmod(ll a, ll b, ll m){
	ll x=1400000000;
	if(m<x) return a*b%m;
	ll m1=m/x, m2=m%x, a1=a/x, a2=a%x, b1=b/x, b2=b%x;
	ll q1=a1*b1/m1, r1=a1*b1%m1;
	ll c=r1*x+a1*b2+a2*b1-q1*m2, d=a2*b2;
	ll q2, r2;
	if(c<0) q2=-(-c+m1)/m1;
	else q2=c/m1;
	r2=c-q2*m1;
	ll ans=r2*x+d-q2*m2;
	if(ans<0) ans=(m-(-ans%m))%m;
	else ans%=m;
	return ans;
}

long long int powmod(long long int a, long long int k, long long int m){
    if(a==0) return 0;
    long long int ap=a, ans=1;
    while(k>0){
        if(k%2==1){
            ans=mulmod(ans, ap, m);
        }
        ap=mulmod(ap, ap, m);
        k/=2;
    }
    return ans;
}
random_device rnd;
mt19937_64 mt(rnd());
bool is_prime(ll n){
    if(n==2){
		return true;
	}
	if(n==1 || n%2==0){
		return false;
	}
	ll d=n-1;
	int k=0;
	while(d%2==0){
		d/=2;
		k++;
	}
	uniform_int_distribution<ll> rndn(2, n-1);
	for(int i=0; i<50; i++){
		ll a=rndn(mt);
		bool comp=1;
		ll ap=powmod(a, d, n);
		if(ap==1 || ap==n-1) continue;
		for(int r=1; r<k; r++){
			ap=mulmod(ap, ap, n);
			if(ap==n-1){
				comp=0;
				break;
			}
		}
		if(comp) return false;
	}
	return true;
}
int main()
{
    sieve();
	int n;
	cin>>n;
	ll a[9];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	ll ans=-1;
	while(1){
		ll p10=1, p=0;
		for(int i=0; i<n; i++){
			p+=(p10*a[i]);
			if(a[i]>=10) p10*=100;
			else p10*=10;
		}
		if(p<MAX){
		    if(isprime[p]) ans=max(ans, p);
		}else{
	    	if(is_prime(p)) ans=max(ans, p);
		}
		if(!next_permutation(a, a+n)) break;
	}
	cout<<ans<<endl;
	return 0;
}
0