結果

問題 No.774 tatyamと素数大富豪
コンテスト
ユーザー mai
提出日時 2018-12-25 08:20:57
言語 cLay
(20241019-1)
結果
AC  
実行時間 1,095 ms / 2,000 ms
コード長 1,823 bytes
コンパイル時間 2,560 ms
コンパイル使用メモリ 174,904 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 13:16:58
合計ジャッジ時間 6,024 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

ll powm_strict(ll x, ll p, ll mod=1000000007ll){
    typedef __int128_t ll128;
    ll y = 1;
    x = x%mod;
    while (0 < p) {
        if (p%2 == 1)
            y = (ll)((((ll128)y)*x)%mod);
        x = (ll)((((ll128)x)*x)%mod);
        p /= 2;
    }
    return y;
}

// Miller–Rabin primality test
// 参考: 
// https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
// https://yukicoder.me/submissions/210680
bool isprime(ll val) {
    typedef __int128_t ll128;
    static ll test[12] = {2,3,5,7,11,13,17,19,23,29,31,37};
    if (val <= 1 || val % 2 == 0)
        return val == 2;
    for (auto t : test)
        if (val % t == 0)
            return val == t;
    if (val < test[11]*test[11])
        return true;
    ll d = val - 1, s = 0;
    while (!(d & 1)) { ++s; d >>= 1; } // d*2**s
    for (auto t : test) {
        ll z = powm_strict(t, d, val);
        if (z == 1 || z == val - 1)
            continue;
        for (ll r = 1; r < s; ++r) {
            z = (ll)((ll128)(z) * z % val);
            if (z == val - 1)
                goto l_isprime_mr_ct;
        }
        return false;
    l_isprime_mr_ct:;
    }
    return true;
}


ll next_perm(vector<int>& buckets, ll val = 0) {
    bool empt = true;
    ll best = -1;
    REP(i, 13){
        if (buckets[i] == 0) continue;
        buckets[i]--;
        if (i <= 8)
            best = max(best, next_perm(buckets, val*10+(i+1)));
        else
            best = max(best, next_perm(buckets, val*100+(i+1)));
        buckets[i]++;
        empt = false;
    }
    
    if (empt)
        return isprime(val) ? val : -1;
    else
        return best;
}


int N;

{
    vector<int> buckets;
    rd(N);
    buckets.resize(13);
    REP(i, N){
        int a; rd(a);
        buckets[a-1]++;
    }
    
    ll ans;
    ans = next_perm(buckets);
    wt(ans);
    
}
0