QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#335980 | #8103. Product | ucup-team1209# | TL | 159ms | 7536kb | C++20 | 1.3kb | 2024-02-24 10:51:22 | 2024-02-24 10:51:22 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = __uint128_t;
using i128 = __int128_t;
std::vector<int> ps;
const int M = 5e5;
u64 pms[M];
int cc;
ll n;
bool ins(u64 x) {
for(int i = 0;i < cc;++i) {
if((i128) pms[i] * x <= n) {
if(cc == M) {
return 0;
}
pms[cc++] = pms[i] * x;
}
}
return 1;
}
int idx;
ll check(ll n) {
for(int i : ps) {
for(;(u64)n % (u32)i == 0;) n /= i;
}
return n == 1;
}
ll ans = 1;
void dfs(ll x, int id) {
if(id < idx) {
ll z = std::upper_bound(pms, pms + cc, n / x)[-1];
ans = std::max(ans, z * x);
return ;
}
for(;;) {
dfs(x, id - 1);
if((i128)x * ps[id] > n) {
break;
}
x *= ps[id];
}
}
void guess(ll n) {
for(int i = 0;i < 2e5 && !check(n);--n, ++i);
if(check(n)) {
cout << n << '\n';
exit(0);
}
}
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
int k; cin >> k >> n;
ps.resize(k);
for(int & x : ps) cin >> x;
guess(n);
*pms = 1, cc = 1;
sort(ps.begin(), ps.end());
for(idx = 0;idx < (int) ps.size();++idx) {
if(!ins(ps[idx])) break;
}
std::sort(pms, pms + cc);
dfs(1, ps.size() - 1);
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
3 30 2 3 7
output:
28
result:
ok 1 number(s): "28"
Test #2:
score: 0
Accepted
time: 25ms
memory: 6272kb
input:
7 939341491978215167 2 3 19 43 47 53 61
output:
939207819748596228
result:
ok 1 number(s): "939207819748596228"
Test #3:
score: 0
Accepted
time: 57ms
memory: 7524kb
input:
16 997257405471326207 2 3 5 11 19 23 37 41 47 53 59 61 73 79 89 97
output:
997257095125632000
result:
ok 1 number(s): "997257095125632000"
Test #4:
score: 0
Accepted
time: 159ms
memory: 7524kb
input:
21 999404092522162547 2 3 13 17 19 23 29 31 37 41 43 47 59 61 67 71 73 79 83 89 97
output:
999404022916180674
result:
ok 1 number(s): "999404022916180674"
Test #5:
score: 0
Accepted
time: 33ms
memory: 7536kb
input:
6 969452367537798143 2 3 5 7 11 13
output:
969402569554298880
result:
ok 1 number(s): "969402569554298880"
Test #6:
score: -100
Time Limit Exceeded
input:
25 999949383078942015 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97