QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163690#4278. GCD vs LCMucup-team004#WA 767ms12536kbC++201.7kb2023-09-04 14:04:092023-09-04 14:04:10

Judging History

你现在查看的是最新测评结果

  • [2023-09-04 14:04:10]
  • 评测
  • 测评结果:WA
  • 用时:767ms
  • 内存:12536kb
  • [2023-09-04 14:04:09]
  • 提交

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'