QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241632#7146. Geometric progression8BQube#TL 981ms125572kbC++201.2kb2023-11-06 14:41:442023-11-06 14:41:45

Judging History

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

  • [2023-11-06 14:41:45]
  • 评测
  • 测评结果：TL
  • 用时：981ms
  • 内存：125572kb
查看
  • [2023-11-06 14:41:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

const int MAXC = 1000000;

vector<int> factor[MAXC + 1];
int vis[MAXC + 1], app[MAXC + 1];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        app[x] = 1;
    }
    for (int i = 1; i <= MAXC; ++i) {
        for (int j = i; j <= MAXC; j += i)
            factor[j].pb(i);
    }
    ll ans = 0;
    for (int i = 1; i <= MAXC; ++i) {
        if (!app[i]) continue;
        for (int j = 1; j < SZ(factor[i]); ++j)
            for (int k = j - 1; k >= 0; --k) {
                // factor[i][k] / factor[i][j]
                //if ((ll)factor[i][k] * factor[i][j] > MAXC) break;
                int ai = i / factor[i][j] * factor[i][k];
                if (vis[ai] == i || !app[ai]) continue;
                ll ak = (ll)i / factor[i][k] * factor[i][j];
                if (ak > MAXC) break;
                vis[ai] = i;
                if (app[ak]) ++ans;
            }
    }
    cout << ans << "\n";
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 616ms
memory: 118124kb

input:

3
1 2 4

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 597ms
memory: 117788kb

input:

4
1 2 4 8

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 631ms
memory: 119480kb

input:

10
4 5 6 7 8 9 10 12 14 15

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 617ms
memory: 118444kb

input:

10
1 3 6 7 8 9 10 12 13 14

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 618ms
memory: 117692kb

input:

10
3 4 5 6 9 11 12 13 14 15

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 622ms
memory: 118112kb

input:

10
1 4 5 6 8 9 10 12 13 14

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 651ms
memory: 118380kb

input:

10
1 2 4 5 7 9 10 11 13 14

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 583ms
memory: 119360kb

input:

10
2 3 4 6 8 9 10 11 14 15

output:

2

result:

ok 1 number(s): "2"

Test #9:

score: 0
Accepted
time: 573ms
memory: 118432kb

input:

10
2 3 4 5 6 8 9 10 13 15

output:

2

result:

ok 1 number(s): "2"

Test #10:

score: 0
Accepted
time: 624ms
memory: 119620kb

input:

10
1 2 3 4 6 8 9 10 14 15

output:

4

result:

ok 1 number(s): "4"

Test #11:

score: 0
Accepted
time: 607ms
memory: 118964kb

input:

10
1 2 4 5 6 7 9 10 13 14

output:

2

result:

ok 1 number(s): "2"

Test #12:

score: 0
Accepted
time: 579ms
memory: 118652kb

input:

10
1 2 3 6 7 8 9 10 12 15

output:

2

result:

ok 1 number(s): "2"

Test #13:

score: 0
Accepted
time: 593ms
memory: 118504kb

input:

1000
1 2 5 6 7 8 9 13 14 15 16 17 18 19 21 24 26 28 31 32 33 34 35 37 40 41 42 43 44 45 46 47 48 50 51 53 54 55 56 58 60 61 63 64 65 68 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 96 97 99 100 103 104 107 109 110 111 112 114 116 117 118 119 120 121 122 123 124 125 126 127...

output:

835

result:

ok 1 number(s): "835"

Test #14:

score: 0
Accepted
time: 650ms
memory: 119588kb

input:

1000
1 2 3 4 5 6 7 9 11 14 15 16 19 21 22 23 27 29 30 31 32 33 34 36 38 39 42 43 46 50 51 52 53 54 56 58 59 61 62 63 64 65 66 67 68 69 71 72 73 74 77 78 79 80 82 83 85 86 87 91 92 93 94 98 99 102 104 107 108 109 110 111 112 113 114 115 116 117 120 122 123 124 126 127 128 129 131 132 134 137 139 141 ...

output:

740

result:

ok 1 number(s): "740"

Test #15:

score: 0
Accepted
time: 584ms
memory: 118036kb

input:

1000
1 2 3 4 6 7 9 10 11 15 16 17 18 19 22 24 25 26 27 29 30 32 33 35 36 37 38 39 42 43 44 45 46 48 50 51 52 53 54 55 59 60 61 63 64 65 67 69 70 71 72 74 77 81 83 84 85 86 87 90 93 95 96 97 101 104 107 108 110 111 112 113 115 116 118 119 124 127 129 130 131 134 135 136 137 140 141 142 143 144 145 14...

output:

792

result:

ok 1 number(s): "792"

Test #16:

score: 0
Accepted
time: 599ms
memory: 118240kb

input:

1000
1 3 6 8 10 12 13 15 16 17 19 20 22 24 25 29 30 31 33 34 36 37 39 41 42 43 49 50 51 52 54 56 57 59 60 61 62 63 64 65 66 68 69 70 73 74 75 77 81 82 84 85 86 87 88 89 93 94 95 96 98 99 102 105 106 107 110 113 115 117 119 120 121 122 124 125 127 128 130 131 132 136 137 138 139 141 142 143 144 145 1...

output:

737

result:

ok 1 number(s): "737"

Test #17:

score: 0
Accepted
time: 623ms
memory: 119004kb

input:

1000
2 5 6 8 9 11 12 13 15 16 17 19 21 24 25 27 28 29 31 33 34 35 36 37 40 44 45 46 47 48 49 50 51 52 53 54 55 56 59 61 62 63 64 65 66 67 68 69 72 73 74 75 76 79 80 81 83 84 86 87 91 93 94 95 96 97 99 100 102 103 104 105 106 107 109 111 113 114 116 117 118 119 120 123 124 125 126 127 128 130 131 132...

output:

752

result:

ok 1 number(s): "752"

Test #18:

score: 0
Accepted
time: 584ms
memory: 118668kb

input:

1000
1 3 6 7 10 11 13 14 15 17 18 19 21 22 23 24 25 26 27 28 31 34 35 36 37 38 40 41 42 43 44 46 48 49 50 51 53 54 56 58 59 60 61 62 65 66 67 69 70 72 73 75 76 79 80 81 83 84 85 89 90 92 93 95 98 101 102 103 104 106 107 108 109 111 112 114 117 118 120 121 122 124 125 130 131 133 134 135 136 137 139 ...

output:

714

result:

ok 1 number(s): "714"

Test #19:

score: 0
Accepted
time: 591ms
memory: 118576kb

input:

1000
1 2 3 4 5 6 8 9 10 11 12 13 14 18 21 22 23 24 26 28 30 31 32 33 36 38 39 40 41 42 44 46 47 48 49 51 55 59 60 64 65 66 67 68 69 70 71 73 75 76 78 79 81 82 83 84 85 88 93 95 98 99 102 103 104 105 106 108 109 110 112 113 116 118 119 120 123 124 125 126 127 131 134 135 138 139 140 141 144 145 146 1...

output:

707

result:

ok 1 number(s): "707"

Test #20:

score: 0
Accepted
time: 598ms
memory: 119400kb

input:

1000
4 5 7 8 9 10 11 14 16 17 18 19 20 23 24 25 27 28 30 33 35 36 37 38 41 43 45 47 48 49 50 51 52 55 61 62 63 64 65 66 69 70 71 72 73 74 75 78 80 81 82 83 88 89 90 91 92 94 95 97 99 102 106 107 109 112 113 115 117 119 120 121 124 125 126 128 129 130 132 133 135 136 137 138 140 143 148 149 150 152 1...

output:

858

result:

ok 1 number(s): "858"

Test #21:

score: 0
Accepted
time: 619ms
memory: 117848kb

input:

1000
1 2 3 4 6 7 8 9 13 14 17 18 19 24 26 27 29 30 31 32 35 36 37 38 39 42 43 44 45 47 48 50 51 53 54 55 59 60 61 62 63 64 66 67 68 69 70 71 72 74 75 79 80 81 84 85 86 87 88 89 90 92 93 94 95 97 100 101 104 105 106 107 108 109 110 113 115 116 117 118 120 121 122 123 124 125 126 129 130 131 132 133 1...

output:

970

result:

ok 1 number(s): "970"

Test #22:

score: 0
Accepted
time: 612ms
memory: 119176kb

input:

1000
1 3 4 5 6 7 8 11 12 13 14 15 16 17 18 20 21 22 23 24 27 28 29 30 35 37 38 39 40 41 44 46 49 50 51 52 54 55 58 59 60 61 62 63 64 65 66 67 68 70 71 73 74 75 76 77 79 80 81 86 87 89 90 91 92 94 96 97 100 101 105 106 107 110 114 115 116 117 118 120 121 122 123 124 125 126 127 128 129 131 134 136 13...

output:

742

result:

ok 1 number(s): "742"

Test #23:

score: 0
Accepted
time: 925ms
memory: 125572kb

input:

500000
1 7 10 12 13 18 19 23 24 26 31 32 33 34 36 37 38 40 43 44 50 57 58 59 60 61 62 63 64 65 66 68 71 74 77 78 79 82 83 84 87 88 90 93 96 97 104 105 106 107 108 109 112 113 117 120 121 126 128 130 132 135 138 139 141 143 144 145 146 148 150 151 155 156 158 160 163 164 170 171 172 173 175 176 177 1...

output:

474875

result:

ok 1 number(s): "474875"

Test #24:

score: 0
Accepted
time: 913ms
memory: 125416kb

input:

500000
2 3 7 9 10 14 16 17 19 32 33 35 39 41 45 46 48 49 50 52 53 56 61 62 63 64 68 69 75 77 79 83 84 85 86 87 88 89 90 97 98 100 102 103 105 107 109 114 116 120 124 125 128 129 130 131 132 135 136 137 141 142 144 145 147 151 152 153 155 156 157 158 162 165 171 172 173 177 178 180 186 188 189 192 19...

output:

458383

result:

ok 1 number(s): "458383"

Test #25:

score: 0
Accepted
time: 966ms
memory: 125336kb

input:

500000
1 3 5 7 8 10 11 16 17 19 24 26 27 34 39 40 41 42 44 45 46 48 51 56 57 58 59 62 65 68 69 71 75 76 77 78 79 80 83 84 88 90 91 94 95 97 98 104 106 107 108 110 118 120 121 127 129 130 131 133 135 137 138 139 142 145 147 151 155 156 158 159 160 161 163 165 166 171 172 173 175 176 177 182 183 185 1...

output:

464913

result:

ok 1 number(s): "464913"

Test #26:

score: 0
Accepted
time: 962ms
memory: 125380kb

input:

500000
2 4 5 6 7 11 12 13 14 15 16 19 23 29 31 32 35 36 37 38 40 42 44 45 46 47 49 50 53 56 59 64 68 69 71 72 73 76 81 82 83 84 86 87 88 89 90 91 92 93 96 98 99 100 106 107 108 109 111 112 113 114 115 116 119 120 121 126 129 131 132 133 135 138 141 143 145 146 148 149 152 155 159 161 162 163 165 166...

output:

469229

result:

ok 1 number(s): "469229"

Test #27:

score: 0
Accepted
time: 973ms
memory: 125424kb

input:

500000
1 2 3 4 5 6 7 8 9 10 13 15 19 21 23 24 25 30 32 34 36 38 39 41 42 45 46 47 49 50 52 53 54 55 57 60 61 62 64 66 67 69 75 76 78 79 81 82 86 88 89 90 92 93 95 96 99 101 102 105 106 113 114 117 119 120 122 123 127 130 131 132 133 138 139 140 142 144 146 148 149 151 152 153 154 155 156 157 158 159...

output:

472480

result:

ok 1 number(s): "472480"

Test #28:

score: 0
Accepted
time: 960ms
memory: 125572kb

input:

500000
1 2 3 9 11 13 14 15 16 18 20 24 30 31 34 36 38 39 40 46 48 50 51 53 55 60 65 66 67 69 70 72 74 75 76 78 79 81 83 84 86 87 88 91 93 94 95 96 97 103 104 106 108 110 111 112 114 119 120 121 128 130 133 138 143 148 150 151 152 155 160 162 165 168 170 174 175 176 177 179 181 182 188 189 190 191 19...

output:

469369

result:

ok 1 number(s): "469369"

Test #29:

score: 0
Accepted
time: 953ms
memory: 125432kb

input:

500000
2 3 4 5 6 7 9 13 15 18 21 24 25 29 30 32 33 34 35 36 37 38 40 41 43 46 49 50 52 55 56 57 59 61 64 65 66 67 68 70 72 73 75 77 78 79 83 85 87 88 91 93 95 96 101 105 107 108 110 113 114 118 119 120 121 122 128 131 134 136 137 138 139 141 143 145 146 148 149 150 158 172 174 175 176 178 179 180 18...

output:

469626

result:

ok 1 number(s): "469626"

Test #30:

score: 0
Accepted
time: 981ms
memory: 125396kb

input:

500000
5 8 9 10 12 13 14 17 18 20 22 23 25 26 27 30 31 32 33 35 41 42 48 52 54 57 59 60 64 65 66 70 71 72 74 77 80 81 84 85 86 88 89 90 92 93 97 101 102 106 107 112 114 116 119 120 121 122 123 125 129 131 133 136 138 140 150 152 153 155 156 157 158 160 164 166 167 168 170 171 173 176 177 179 184 185...

output:

473306

result:

ok 1 number(s): "473306"

Test #31:

score: -100
Time Limit Exceeded

input:

500000
1 3 4 6 7 12 14 15 18 19 21 22 23 25 27 30 31 34 40 41 43 46 47 48 50 51 52 55 56 57 58 59 62 63 65 67 69 70 71 72 73 75 76 77 78 80 83 85 86 87 88 89 90 92 93 95 97 103 106 107 108 111 112 113 114 115 116 117 118 120 122 123 124 126 128 129 130 132 133 134 135 136 138 139 141 142 143 144 146...

output:

465139

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 01:33:23 | OpenSource Project