QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#371254 | #7797. Based Zeros | FOY# | TL | 4ms | 3800kb | C++17 | 1.5kb | 2024-03-30 03:21:19 | 2024-03-30 03:21:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const ull MAX = 32000;
const ull MAX_2 = 1e6 + 1000;
pair<ull, ull> cntZ(ull n, ull b) {
ull out = 0;
ull bits = 0;
while (n) {
if (n%b == 0) out++;
n /= b;
bits++;
}
return { out, bits };
}
ull pow(ull base, ull exp) {
ull out = 1;
for (ull i = 0; i < exp; i++) {
out *= base;
}
return out;
}
map<ull, pair<ull, ull>> ans;
map<ull, vector<ull>> memo;
void solve() {
ull n;
cin >> n;
if (ans.count(n) != 0) {
cout << ans[n].first << " " << ans[n].second << endl;
for (ull b : memo[n]) {
cout << b << " ";
}
cout << endl;
return;
}
ull max_zeros = 0;
vector<ull> res;
for (ull b = 2; b <= MAX && b <= n; b++) {
pair<ull, ull> cnt = cntZ(n, b);
if (cnt.first > max_zeros) {
res.clear();
res.push_back(b);
max_zeros = cnt.first;
} else if (cnt.first == max_zeros) {
res.push_back(b);
}
}
for (ull b = MAX + 1; b <= MAX_2 && b <= n; b++) {
pair<ull, ull> cnt = cntZ(n, b);
if (cnt.first > max_zeros) {
res.clear();
res.push_back(b);
max_zeros = cnt.first;
} else if (cnt.first == max_zeros) {
res.push_back(b);
}
}
ans[n] = make_pair(max_zeros, res.size());
memo[n] = res;
cout << max_zeros << " " << res.size() << endl;
for (ull c : res) {
cout << c << " ";
}
cout << endl;
}
signed main() {
ull t;
cin >> t;
while (t--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
3 11 1007 239
output:
1 3 2 3 11 2 2 3 10 1 4 2 6 15 239
result:
ok 15 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1 2
output:
1 1 2
result:
ok 3 number(s): "1 1 2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
10 56 20 6 84 25 20 60 73 70 50
output:
3 1 2 3 1 2 1 3 2 3 6 4 1 2 2 2 2 5 3 1 2 2 2 2 3 4 1 2 4 1 2 3 1 2
result:
ok 34 numbers
Test #4:
score: 0
Accepted
time: 4ms
memory: 3584kb
input:
100 6211 4783 6225 5664 9709 5455 5424 7394 2329 3880 8260 950 2604 1366 3080 5505 4983 9595 6563 2697 2249 675 1537 5884 6070 2905 3137 5675 8138 1626 5348 8876 6065 8454 9346 3421 8857 8941 2743 9343 6201 45 1651 8575 5327 2577 4553 7595 1185 8775 7241 616 4465 3642 1657 5791 2800 1669 9307 2640 6...
output:
8 1 2 5 1 2 8 1 2 9 1 2 5 1 2 5 1 2 8 1 2 6 1 2 7 1 2 6 1 2 11 1 2 3 1 2 7 1 2 5 1 2 9 1 2 8 1 2 4 1 2 5 1 2 7 1 3 7 1 2 7 1 2 5 1 2 8 1 2 4 1 2 4 1 2 5 1 2 8 1 2 6 1 2 4 1 2 5 1 2 7 1 2 8 1 2 5 1 2 10 1 2 10 1 2 4 1 2 8 1 2 6 1 2 4 1 2 5 1 2 7 1 2 2 2 2 3 4...
result:
ok 309 numbers
Test #5:
score: -100
Time Limit Exceeded
input:
1000 461349 350342 809551 211152 572968 896101 718511 44614 72871 106360 141199 858436 576392 414585 897161 917037 679916 987675 507878 851589 62793 717573 119037 587678 774831 977964 313698 208868 953676 26986 273250 625834 573172 865274 105345 290197 807126 566514 193786 645978 670847 961765 72414...
output:
11 1 2 11 1 2 9 1 2 10 1 2 11 1 2 9 1 2 6 1 2 8 1 2 8 1 2 6 1 2 8 1 2 12 1 2 12 1 2 8 1 2 11 1 2 6 1 2 7 1 2 10 1 2 4 2 2 3 8 1 2 7 1 2 10 1 2 6 1 2 7 1 2 7 1 2 9 1 2 11 1 2 7 1 2 10 1 2 7 1 2 11 1 2 11 1 2 8 1 2 7 1 2 9 1 2 9 1 2 11 1 2 11 1 2 6 1 2 8 1 2 7 1...