QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692500 | #9248. An Easy Math Problem | KeeperHihi# | TL | 263ms | 3864kb | C++20 | 1001b | 2024-10-31 14:37:45 | 2024-10-31 22:43:11 |
Judging History
This is the latest submission verdict.
- [2024-10-31 22:36:43]
- hack成功,自动添加数据
- (/hack/1098)
- [2024-10-31 22:13:58]
- hack成功,自动添加数据
- (/hack/1096)
- [2024-10-31 22:00:43]
- hack成功,自动添加数据
- (/hack/1095)
- [2024-10-31 14:37:45]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
map<i64, int> Map;
void solve() {
i64 n;
cin >> n;
if (Map.count(n)) {
cout << Map[n] << "\n";
return;
}
vector<i64> p;
for (i64 i = 1; i * i <= n; i++) {
if (n % i == 0) {
p.emplace_back(i);
if (i * i != n) {
p.emplace_back(n / i);
}
}
}
sort(p.begin(), p.end());
int m = p.size();
int cnt = 0;
unordered_set<i64> set;
for (auto t : p) set.insert(t);
for (int i = 0; i < m; i++) {
if (p[i] > sqrt(n) + 1) break;
int t = lower_bound(p.begin(), p.end(), p[i] * p[i]) - p.begin();
for (int j = t; j < m; j++) {
if (p[j] % p[i] == 0 && set.find(p[j] / p[i]) != set.end()) {
if (gcd(p[i], p[j] / p[i]) == 1) {
cnt++;
}
}
}
}
cout << cnt << "\n";
Map[n] = cnt;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 2 3 2 5 2 4 3 5
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2000 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 646969323...
output:
29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 ...
result:
ok 2000 lines
Test #3:
score: 0
Accepted
time: 263ms
memory: 3864kb
input:
2000 1763047095 79735483 1016286871 2864801397 2327774116 2668010360 3469893354 3634459021 1613699068 781737219 574741575 2763134701 1458502604 1822260248 2281150332 2924219311 2493931196 3735904708 158802001 2006921221 729928782 1974841034 727412600 2873393292 1291087179 2741607663 1893408215 29827...
output:
14 5 2 5 23 95 68 14 8 68 203 14 23 32 38 41 8 8 14 2 608 41 158 338 23 41 14 5 14 41 14 203 41 14 17 446 5 53 59 878 2 14 365 203 14 203 2 122 32 95 41 41 5 23 14 41 5 5 14 122 23 203 608 23 41 122 2 14 95 2 68 41 203 14 230 41 68 23 50 14 32 14 8 5 5 5 68 68 122 293 473 5 41 41 14 2 14 14 5 2 122 ...
result:
ok 2000 lines
Extra Test:
score: -3
Extra Test Failed : Time Limit Exceeded on 4
input:
2000 10000000000 9999980000 9999960000 9999940000 9999920000 9999900000 9999880000 9999860000 9999840000 9999820000 9999800000 9999780000 9999760000 9999740000 9999720000 9999700000 9999680000 9999660000 9999640000 9999620000 9999600000 9999580000 9999560000 9999540000 9999520000 9999500000 99994800...
output:
221 743 1580 446 1013 2723 527 446 2066 446 215 4010 608 446 3686 908 257 4010 1580 446 2228 149 176 2228 230 644 1580 149 1013 446 1073 149 5468 446 1580 545 203 446 1580 4010 842 1040 527 149 1823 182 4739 1337 257 446 3803 446 203 6683 176 182 2066 149 176 2228 743 1337 1580 446 851 545 176 446 1...