結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー | ceni1055 |
提出日時 | 2018-12-22 00:38:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,404 bytes |
コンパイル時間 | 1,839 ms |
コンパイル使用メモリ | 178,016 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-25 09:48:24 |
合計ジャッジ時間 | 5,959 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 18 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 29 ms
6,944 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 17 ms
6,940 KB |
testcase_15 | WA | - |
testcase_16 | AC | 8 ms
6,944 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
ソースコード
#include <bits/stdc++.h> #include <assert.h> using namespace std; long long powMod(long long x, long long k, long long m) { if (k == 0) return 1; if (k % 2 == 0) return powMod(x * x % m, k / 2, m); else return x * powMod(x, k - 1, m) % m; } bool suspect(long long a, int s, long long d, long long n) { long long x = powMod(a, d, n); if (x == 1) return true; for (int r = 0; r < s; ++r) { if (x == n - 1) return true; x = x * x % n; } return false; } // {2,7,61,-1} is for n < 4759123141 (= 2^32) // {2,3,5,7,11,13,17,19,23,-1} is for n < 10^16 (at least) bool isPrime(long long n) { if (n <= 1 || (n > 2 && n % 2 == 0)) return false; int test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, -1}; long long d = n - 1, s = 0; while (d % 2 == 0) ++s, d /= 2; for (int i = 0; test[i] < n && test[i] != -1; ++i) if (!suspect(test[i], s, d, n)) return false; return true; } int main() { int n; cin >> n; vector<string> a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end()); long long ans = 0; do { string tmp; for (int i = 0; i < n; i++) tmp += a[i]; long long check = stoll(tmp); cerr << check << endl; if (isPrime(check)) ans = max(ans, check); } while (next_permutation(a.begin(), a.end())); cout << (ans == 0 ? -1 : ans) << endl; return 0; }