結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー |
![]() |
提出日時 | 2018-12-22 00:11:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,985 bytes |
コンパイル時間 | 864 ms |
コンパイル使用メモリ | 65,332 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-10-01 13:21:31 |
合計ジャッジ時間 | 9,259 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 13 TLE * 1 |
ソースコード
#include <stdio.h> #include <algorithm> #include <vector> #include <set> using namespace std; using lint = long long; lint gcd(lint a, lint b) { return b ? gcd(b,a%b) : a; } namespace miller_rabin{ lint mul(lint x, lint y, lint mod){ return (__int128) x * y % mod; } lint ipow(lint x, lint y, lint p){ lint ret = 1, piv = x % p; while(y){ if(y&1) ret = mul(ret, piv, p); piv = mul(piv, piv, p); y >>= 1; } return ret; } bool miller_rabin(lint x, lint a){ if(x % a == 0) return 0; lint d = x - 1; while(1){ lint tmp = ipow(a, d, x); if(d&1) return (tmp != 1 && tmp != x-1); else if(tmp == x-1) return 0; d >>= 1; } } bool isprime(lint x){ for(auto &i : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}){ if(x == i) return 1; if(x > 40 && miller_rabin(x, i)) return 0; } if(x <= 40) return 0; return 1; } } namespace pollard_rho{ lint f(lint x, lint n, lint c){ return (c + miller_rabin::mul(x, x, n)) % n; } void rec(lint n, vector<lint> &v){ if(n == 1) return; if(n % 2 == 0){ v.push_back(2); rec(n/2, v); return; } if(miller_rabin::isprime(n)){ v.push_back(n); return; } lint a, b, c; while(1){ a = rand() % (n-2) + 2; b = a; c = rand() % 20 + 1; do{ a = f(a, n, c); b = f(f(b, n, c), n, c); }while(gcd(abs(a-b), n) == 1); if(a != b) break; } lint x = gcd(abs(a-b), n); rec(x, v); rec(n/x, v); } vector<lint> factorize(lint n){ vector<lint> ret; rec(n, ret); sort(ret.begin(), ret.end()); return ret; } }; int main() { int N; scanf ("%d",&N); int A[10]; for (int i=0;i<N;i++) scanf ("%d",&A[i]); long long ans = -1; set<long long> chk; do{ long long a = 0; for (int i=0;i<N;i++){ if (A[i] < 10) a = a * 10 + A[i]; else a = a * 100 + A[i]; } if (chk.count(a)) continue; else{ chk.insert(a); if (miller_rabin::isprime(a)) ans = max(ans,a); } }while(next_permutation(A,A+N)); printf ("%lld\n",ans); return 0; }