結果

問題 No.774 tatyamと素数大富豪
ユーザー chocorusk
提出日時 2018-12-22 00:47:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,198 bytes
コンパイル時間 1,088 ms
コンパイル使用メモリ 100,792 KB
実行使用メモリ 12,128 KB
最終ジャッジ日時 2024-10-01 13:21:41
合計ジャッジ時間 7,519 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 13 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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<20; 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0