結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー |
![]() |
提出日時 | 2019-04-04 12:53:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,003 ms / 2,000 ms |
コード長 | 1,837 bytes |
コンパイル時間 | 2,379 ms |
コンパイル使用メモリ | 172,056 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 21:31:29 |
合計ジャッジ時間 | 6,405 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#include "bits/stdc++.h"using namespace std;#ifdef _DEBUG#include "dump.hpp"#include <boost/multiprecision/cpp_int.hpp>namespace mp = boost::multiprecision;using u128 = mp::cpp_int;#else#define dump(...)using u128 = __uint128_t;#endif//#define int long long#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)#define all(c) begin(c),end(c)const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;const int MOD = 1'000'000'007;template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }template<typename T>T modpow(T a, T e, T mod) {T res = 1;while (e > 0) {if (e & 1)res = res * a % mod; // modmul(res, a, mod);a = a * a % mod; // modmul(a, a, mod);e >>= 1;}return res;}template<typename T>bool millerRabinPrimalityTest(T n, int iteration = 5) {if (n < 2)return false;if (n == 2)return true;if (n % 2 == 0)return false;T d = n - 1;while (d % 2 == 0)d /= 2;for (int i = 0; i < iteration; i++) {T a = rand() % (n - 1) + 1, t = d;T mod = modpow(a, t, n);while (t != n - 1 && mod != 1 && mod != n - 1) {mod = mod * mod % n; //modmul(mod, mod, n);t *= 2;}if (mod != n - 1 && t % 2 == 0)return false;}return true;}signed main() {cin.tie(0);ios::sync_with_stdio(false);int n; cin >> n;vector<int> a(n); rep(i, 0, n) {cin >> a[i];}sort(all(a));long long ans = -1;do {long long x = 0;rep(i, 0, n) {if (a[i] >= 10) {x *= 100;x += a[i];}else {x *= 10;x += a[i];}}if (millerRabinPrimalityTest(u128(x)))chmax(ans, x);} while (next_permutation(all(a)));cout << ans << endl;return 0;}