結果

問題 No.774 tatyamと素数大富豪
ユーザー mai
提出日時 2018-12-25 08:20:57
言語 cLay
(20241019-1)
結果
AC  
実行時間 1,095 ms / 2,000 ms
コード長 1,823 bytes
コンパイル時間 2,560 ms
コンパイル使用メモリ 174,904 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 13:16:58
合計ジャッジ時間 6,024 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

ll powm_strict(ll x, ll p, ll mod=1000000007ll){
typedef __int128_t ll128;
ll y = 1;
x = x%mod;
while (0 < p) {
if (p%2 == 1)
y = (ll)((((ll128)y)*x)%mod);
x = (ll)((((ll128)x)*x)%mod);
p /= 2;
}
return y;
}
// Miller–Rabin primality test
// :
// https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
// https://yukicoder.me/submissions/210680
bool isprime(ll val) {
typedef __int128_t ll128;
static ll test[12] = {2,3,5,7,11,13,17,19,23,29,31,37};
if (val <= 1 || val % 2 == 0)
return val == 2;
for (auto t : test)
if (val % t == 0)
return val == t;
if (val < test[11]*test[11])
return true;
ll d = val - 1, s = 0;
while (!(d & 1)) { ++s; d >>= 1; } // d*2**s
for (auto t : test) {
ll z = powm_strict(t, d, val);
if (z == 1 || z == val - 1)
continue;
for (ll r = 1; r < s; ++r) {
z = (ll)((ll128)(z) * z % val);
if (z == val - 1)
goto l_isprime_mr_ct;
}
return false;
l_isprime_mr_ct:;
}
return true;
}
ll next_perm(vector<int>& buckets, ll val = 0) {
bool empt = true;
ll best = -1;
REP(i, 13){
if (buckets[i] == 0) continue;
buckets[i]--;
if (i <= 8)
best = max(best, next_perm(buckets, val*10+(i+1)));
else
best = max(best, next_perm(buckets, val*100+(i+1)));
buckets[i]++;
empt = false;
}
if (empt)
return isprime(val) ? val : -1;
else
return best;
}
int N;
{
vector<int> buckets;
rd(N);
buckets.resize(13);
REP(i, N){
int a; rd(a);
buckets[a-1]++;
}
ll ans;
ans = next_perm(buckets);
wt(ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0