結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー |
|
提出日時 | 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 |
ソースコード
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/210680bool 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**sfor (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)));elsebest = max(best, next_perm(buckets, val*100+(i+1)));buckets[i]++;empt = false;}if (empt)return isprime(val) ? val : -1;elsereturn 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);}