QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163690 | #4278. GCD vs LCM | ucup-team004# | WA | 767ms | 12536kb | C++20 | 1.7kb | 2023-09-04 14:04:09 | 2023-09-04 14:04:10 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
constexpr int N = 1E5;
constexpr int V = 1000;
int mu[N + 1];
i64 s[N + 1];
i64 f[V + 1][V + 1];
void solve() {
int n, m, a;
std::cin >> n >> m >> a;
if (n > m) {
std::swap(n, m);
}
a = std::min(a, n);
i128 ans = 0;
for (int ld = 1, rd; ld <= a; ld = rd + 1) {
int nd = n / ld;
int md = m / ld;
rd = std::min({n / nd, m / md, a});
i128 res = 0;
if (md <= V) {
res = f[nd][md];
} else {
for (int lx = 1, rx; lx <= nd; lx = rx + 1) {
int nx = nd / lx;
int mx = md / lx;
rx = std::min(nd / nx, md / mx);
res += i128(s[rx] - s[lx - 1]) * nx * (nx + 1) * mx * (mx + 1) / 4;
}
}
ans += i128(ld + rd) * (rd - ld + 1) / 2 * res;
}
std::string s;
while (ans > 0) {
s += '0' + ans % 10;
ans /= 10;
}
std::reverse(s.begin(), s.end());
std::cout << s << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
mu[1] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 2 * i; j <= N; j += i) {
mu[j] -= mu[i];
}
}
for (int i = 1; i <= N; i++) {
s[i] = s[i - 1] + 1LL * mu[i] * i * i;
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + (std::gcd(i, j) == 1) * i * j;
}
}
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 24ms
memory: 12392kb
input:
2 2 2 1 3 4 2
output:
5 45
result:
ok 2 number(s): "5 45"
Test #2:
score: 0
Accepted
time: 27ms
memory: 12472kb
input:
5 2 8 4 10 2 9 7 8 3 2 5 10 5 2 4
output:
88 135 742 39 39
result:
ok 5 number(s): "88 135 742 39 39"
Test #3:
score: 0
Accepted
time: 31ms
memory: 12476kb
input:
5 17 8 8 27 17 10 38 46 2 37 42 1 46 13 1
output:
4164 43084 548829 385452 61783
result:
ok 5 number(s): "4164 43084 548829 385452 61783"
Test #4:
score: 0
Accepted
time: 28ms
memory: 12536kb
input:
10 73 49 10 9 84 15 22 19 17 83 54 6 30 23 9 97 2 4 28 73 9 26 40 11 97 48 7 49 45 18
output:
2437081 119216 35475 3776013 94357 11907 794038 207296 4053849 928605
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 24ms
memory: 12404kb
input:
100 75 26 130 70 18 15 109 93 55 69 196 40 180 90 153 188 82 45 167 130 110 77 68 32 56 157 79 156 174 97 190 42 82 69 107 57 152 57 183 107 156 18 73 177 90 122 5 160 108 192 147 173 157 28 39 25 45 117 191 73 8 2 166 66 18 51 76 12 78 90 181 172 40 24 84 23 158 37 7 124 134 170 171 111 62 200 198 ...
output:
733546 306373 19237886 34028538 48568920 44112548 87408560 5156750 14409270 135732487 11858723 10249690 14001574 51643353 31220267 88419 79432066 136817339 186804 92568248 88 273073 164650 49310115 177044 2583670 166176 156075703 28836450 163355481 12190226 2976316 3587981 199736999 20671629 5515762...
result:
ok 100 numbers
Test #6:
score: -100
Wrong Answer
time: 767ms
memory: 12416kb
input:
10000 60891 25901 72 66133 58189 144 80100 76127 113 56312 7713 20 15505 43545 83 4224 92681 67 86783 58363 95 40265 24699 18 87356 47123 54 30695 14987 197 52463 10356 157 84648 26368 16 50778 80419 99 46382 49146 34 50613 56280 189 86933 38991 186 80758 7552 90 71787 67827 168 83791 19979 96 46722...
output:
454410093465275548 2705485122034769594 6792940506085892554 34435356702147437 83280855424750523 28001980141909957 4686610150694356661 180484338953162315 3095471755633370023 38666143651557218 53930110736125525 908776499719663271 3046354571627118247 948984591080075271 1482373064064778524 20990612734018...
result:
wrong answer 1st numbers differ - expected: '284404918', found: '454410093465275548'