結果

問題 No.774 tatyamと素数大富豪
ユーザー chocoruskchocorusk
提出日時 2018-12-22 00:51:50
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,614 ms / 2,000 ms
コード長 2,198 bytes
コンパイル時間 978 ms
コンパイル使用メモリ 100,796 KB
実行使用メモリ 12,256 KB
最終ジャッジ日時 2024-10-01 13:21:49
合計ジャッジ時間 6,614 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,614 ms
12,128 KB
testcase_01 AC 46 ms
12,128 KB
testcase_02 AC 45 ms
12,124 KB
testcase_03 AC 46 ms
12,128 KB
testcase_04 AC 46 ms
12,120 KB
testcase_05 AC 44 ms
12,128 KB
testcase_06 AC 46 ms
12,120 KB
testcase_07 AC 45 ms
12,120 KB
testcase_08 AC 45 ms
12,128 KB
testcase_09 AC 44 ms
12,128 KB
testcase_10 AC 45 ms
12,124 KB
testcase_11 AC 52 ms
12,124 KB
testcase_12 AC 691 ms
12,256 KB
testcase_13 AC 318 ms
12,124 KB
testcase_14 AC 47 ms
12,120 KB
testcase_15 AC 57 ms
12,124 KB
testcase_16 AC 46 ms
12,124 KB
testcase_17 AC 48 ms
12,004 KB
testcase_18 AC 52 ms
12,120 KB
権限があれば一括ダウンロードができます

ソースコード

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){
    for(int i=0; i<10; i++){
        if(n%prime[i]==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<10; 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