結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー |
![]() |
提出日時 | 2019-03-23 02:37:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 990 ms / 2,000 ms |
コード長 | 2,623 bytes |
コンパイル時間 | 1,547 ms |
コンパイル使用メモリ | 171,832 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 16:25:02 |
合計ジャッジ時間 | 5,078 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) REP(i,0,n)#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)#define repr(i, n) REPR(i, n, 0)#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)#define pb push_back#define all(r) r.begin(),r.end()#define rall(r) r.rbegin(),r.rend()#define fi first#define se secondtypedef long long ll;typedef vector<int> vi;typedef vector<ll> vl;typedef pair<int, int> pii;typedef pair<ll, ll> pll;const int INF = 1e9;const ll MOD = 1e9 + 7;double EPS = 1e-8;using u32 = unsigned int;using u64 = unsigned long long;using u128 = __uint128_t;template <class Uint, class BinOp>bool is_prime_impl(const Uint &n, const Uint *witness, BinOp modmul) {if (n == 2) return true;if (n < 2 || n % 2 == 0) return false;const Uint m = n - 1, d = m / (m & -m);auto modpow = [&](Uint a, Uint b) {Uint res = 1;for (; b; b /= 2) {if (b & 1) res = modmul(res, a);a = modmul(a, a);}return res;};auto suspect = [&](Uint a, Uint t) {a = modpow(a, t);while (t != n - 1 && a != 1 && a != n - 1) {a = modmul(a, a);t = modmul(t, 2);}return a == n - 1 || t % 2 == 1;};for (const Uint *w = witness; *w; w++) {if (*w % n != 0 && !suspect(*w, d)) return false;}return true;}bool is_prime(const u128 &n) {assert(n < 1ULL << 63);if (n < 1ULL << 32) {// n < 2^32constexpr u64 witness[] = {2, 7, 61, 0};auto modmul = [&](u64 a, u64 b) { return a * b % n; };return is_prime_impl<u64>(n, witness, modmul);} else {// n < 2^63constexpr u128 witness[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0};// if u128 is availableauto modmul = [&](u128 a, u128 b) { return a * b % n; };// otherwise// auto modmul = [&](u64 a, u64 b) {// u64 res = 0;// for (; b; b /= 2) {// if (b & 1) res = (res + a) % n;// a = (a + a) % n;// }// return res;// };return is_prime_impl<u128>(n, witness, modmul);}}int main(){int n;cin >> n;vl a(n);rep(i, n) cin >> a[i];ll ans = -1LL;do {ll tmp = 0LL;rep(i, n) {if(a[i] > 9) tmp *= 100;else tmp *= 10;tmp += a[i];}if(is_prime(tmp)) ans = max(ans, tmp);}while(next_permutation(all(a)));cout << ans << endl;return 0;}