結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー | mai |
提出日時 | 2018-12-25 08:20:57 |
言語 | cLay (20240714-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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,095 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 8 ms
5,376 KB |
testcase_12 | AC | 450 ms
5,376 KB |
testcase_13 | AC | 198 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 10 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 4 ms
5,376 KB |
testcase_18 | AC | 6 ms
5,376 KB |
ソースコード
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); }