ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215233 | #2643. gcd | KXG | 10 | 1393ms | 18296kb | C++11 | 1.9kb | 2024-11-27 19:20:03 | 2024-11-27 23:36:29 |
answer
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
struct GCDRMQ {
int n;
long long a[100010];
long long f[20][100010];
void init() {
for (int i = 1; i <= n; i++) {
f[0][i] = a[i];
}
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
if (j + (1 << (i - 1)) > n) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = gcd(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
}
}
}
long long query(long long l, long long r) {
int i = log2(r - l + 1);
return gcd(f[i][l], f[i][r - (1 << i) + 1]);
}
} gr;
int n, q;
long long a[100010], x;
map<long long, long long> mp;
pair<int, long long> findr(int l, int r) {
long long now = gr.query(l, r);
int L = r, R = n, ans;
while (L <= R) {
int mid = (L + R) >> 1;
if (gr.query(l, mid) == now) {
ans = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
return {ans, now};
}
int main() {
scanf("%d", &n);
gr.n = n;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
gr.a[i] = a[i];
}
gr.init();
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j < n; j++) {
pair<int, long long> res = findr(i, j + 1);
int r = res.first;
long long v = res.second;
mp[v] += r - j;
j = r;
}
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%d", &x);
if (!mp.count(x)) printf("0\n");
else printf("%lld\n", mp[x]);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 52ms
memory: 1380kb
input:
1071 546 2340 8190 420 6300 1050 40950 25 23400 195 2340 630 195 40950 2184 504 525 130 2340 1800 39...
output:
14 567964 95 142 43 61 142 43 920 567964 14 103 12 72 142 61 920 567964 142 142 567964 578 95 43 43 ...
result:
wrong answer 1st lines differ - expected: '29', found: '14'
Test #2:
score: 0
Wrong Answer
time: 52ms
memory: 1688kb
input:
2878 728 50 420 4200 25 200 4 81900 546 195 11700 900 900 42 1092 520 6 36 6552 150 18200 130 585 28...
output:
116 298 353 72 3059 1029 116 119 72 353 72 317 73 237 317 4126338 72 298 116 4126338 4126338 1029 30...
result:
wrong answer 1st lines differ - expected: '183', found: '116'
Test #3:
score: 0
Wrong Answer
time: 56ms
memory: 1488kb
input:
1685 1365 225 40 9 3900 3900 2100 105 120 25 8 2184 2184 10 2100 23400 780 600 325 32760 4680 260 39...
output:
1411203 1270 157 29 722 1411203 1411203 722 51 234 157 126 51 636 49 55 51 1411203 55 164 636 164 63...
result:
wrong answer 1st lines differ - expected: '1412451', found: '1411203'
Test #4:
score: 0
Wrong Answer
time: 62ms
memory: 1788kb
input:
3492 1820 9100 45 8190 72 50 3276 260 14 8 24 65 910 5850 150 520 23400 520 700 2730 300 72 728 70 2...
output:
1537 1537 1525 2413 86 403 86 75 398 2413 389 1537 6079383 2413 86 107 1537 389 269 389 1537 398 107...
result:
wrong answer 1st lines differ - expected: '1954', found: '1537'
Test #5:
score: 0
Wrong Answer
time: 224ms
memory: 12464kb
input:
65614 4680 3900 2340 6825 5 1560 780 12600 75 140 156 50 3276 182 315 52 5460 40950 20475 14 78 2340...
output:
7332 1049 1049 7007 2252 2240 7007 2152258449 7007 7007 1049 4671 6968 2231 2152258449 7007 6968 264...
result:
wrong answer 1st lines differ - expected: '10574', found: '7332'
Test #6:
score: 0
Wrong Answer
time: 311ms
memory: 18240kb
input:
99228 11700 1400 35 1260 2520 975 56 100 18200 468 20 1560 450 900 36 468 9 4 56 650 195 3 468 4680 ...
output:
11109 1618 10611 40184 3200 11097 7430 7430 11109 3184 40184 11097 10611 11097 3184 3341 40184 1618 ...
result:
wrong answer 1st lines differ - expected: '16046', found: '11109'
Test #7:
score: 0
Wrong Answer
time: 113ms
memory: 5660kb
input:
26035 39 900 315 1400 130 2600 7800 4095 234 36 200 25 312 1092 252 780 90 23400 1 4680 104 2 54600 ...
output:
10764 364 3078 3078 2941 3078 789 2914 364 10261 2914 1765 786 789 3078 10261 2941 3078 1765 1765 33...
result:
wrong answer 1st lines differ - expected: '13708', found: '10764'
Test #8:
score: 0
Wrong Answer
time: 148ms
memory: 8560kb
input:
42842 468 325 390 1 120 150 6552 60 840 780 7800 126 35 140 40950 81900 6300 75 1050 210 6300 700 45...
output:
4612 1460 4875 917494270 1460 1363 917494270 3302 1363 1487 917494270 917494270 4944 1363 4875 4944 ...
result:
wrong answer 1st lines differ - expected: '6626', found: '4612'
Test #9:
score: 0
Wrong Answer
time: 237ms
memory: 14344kb
input:
76456 8190 700 32760 27300 2100 24 3 126 1820 150 280 9100 104 3900 520 27300 65 1638 4095 273 450 1...
output:
8651 2922359943 8546 8322 5480 2543 30038 8651 2596 1148 2543 2520 32858 30038 2922359943 2543 5480 ...
result:
wrong answer 1st lines differ - expected: '12422', found: '8651'
Test #10:
score: 10
Accepted
time: 138ms
memory: 18296kb
input:
100000 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...
output:
5000050000 5000050000 5000050000 5000050000 5000050000 5000050000 5000050000 5000050000 5000050000 5...
result:
ok 300000 lines