結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー |
![]() |
提出日時 | 2018-12-22 19:34:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,235 bytes |
コンパイル時間 | 1,797 ms |
コンパイル使用メモリ | 171,344 KB |
実行使用メモリ | 16,960 KB |
最終ジャッジ日時 | 2024-10-01 13:23:59 |
合計ジャッジ時間 | 8,188 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 5 |
other | TLE * 1 -- * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>T gcd(T a, T b){while (b){T tmp = b;b = a % b;a = tmp;}return a;}template <typename T>T pow_mod(T a, T n, T mod){T r = 1;for (; n; n >>= 1){if (n & 1){(r *= a) %= mod;}(a *= a) %= mod;}return r;}template <typename T>bool miller_rabin(T n){if (n < 2){return false;}for (T a = 2; a < min(T(15), n); a++){if (gcd(a, n) != 1){continue;}T m = n - 1;if (pow_mod(a, m, n) != 1){return false;}for (m >>= 1; m % 2 == 0; m >>= 1){T puni = pow_mod(a, m, n);if (puni == n - 1){break;}if (puni != 1){return false;}}T puni = pow_mod(a, m, n);if ((puni != n - 1) && (puni != 1)){return false;}}return true;}int main(){int n;cin >> n;vector<int> as(n);for (auto &a : as){cin >> a;}int64_t ans = -1;do{string s = "";for (auto &a : as){s += to_string(a);}__int128_t x = 0;for (auto &c : s){x *= 10;x += c - '0';}if (miller_rabin(x)){ans = max(ans, int64_t(x));}} while (next_permutation(as.begin(), as.end()));cout << ans << endl;return 0;}