ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215234 | #2643. gcd | N | 100 | 639ms | 15652kb | C++11 | 3.0kb | 2024-11-27 19:30:22 | 2024-11-27 23:36:34 |
answer
//
// na 2643.cpp
// Competitive Programming
//
// Created by m2 on 2024/11/27.
//
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
typedef long long int ll;
using namespace std;
const int maxn = 1e5 + 5, maxdep = 17;
int n, q, lg2[maxn];
ll a[maxn], st[maxn][maxdep];
//set<pair<ll, int> > v[2];
//set<pair<ll, int> > *lv = &v[0], *nv = &v[1];
map<ll, ll> ans;
template<typename T> inline void rd(T &v){
v = 0; char r = getchar();
while(r - 48 >= 10u)
r = getchar();
while(r - 48 < 10u){
v = (v << 3) + (v << 1) + (r ^ 48);
r = getchar();
}
}
template<typename T> void pd(T v){
if(v < 10)
putchar(int(v) ^ 48);
else{
pd(v / 10);
putchar(int(v % 10) ^ 48);
}
}
template<typename T> T gcd(T a, T b){ return b? gcd(b, a % b): a; }
inline void init_st(){
for(int i = n; i; --i){
st[i][0] = a[i];
for(int j = 1; j < maxdep; ++j)
st[i][j] = gcd(st[i][j - 1], st[min(n, i + (1 << (j - 1)))][j - 1]);
}
lg2[1] = 0;
for(int i = 2; i <= n; ++i)
lg2[i] = lg2[i >> 1] + 1;
}
inline ll query(int lt, int rt){
int dep = lg2[rt - lt + 1];
return gcd(st[lt][dep], st[rt - (1 << dep) + 1][dep]);
}
#ifdef MAC_OS_VERSION_11_0
//#define BRUTEFORCE
#endif
int main(){
cin.tie(0)->sync_with_stdio(false);
rd(n);
for(int i = 1; i <= n; ++i){
rd(a[i]);
// cerr << "fin" << i << endl;
}
init_st();
// nv->insert(make_pair(a[1], 1));
// ans[a[1]] = 1;
// for(int i = 2; i <= n; ++i){
// swap(nv, lv);
// nv->clear();
// nv->insert(make_pair(a[i], 1));
// for(auto iter = lv->begin(); iter != lv->end(); ++iter){
// ll val = gcd(iter->first, a[i]);
// int cnt = iter->second;
// auto ptr = nv->lower_bound(make_pair(val, 0));
// if(ptr != nv->end() && ptr->first == val){
// cnt += ptr->second;
// nv->erase(ptr);
// }
// nv->insert(make_pair(val, cnt));
// }
// for(auto iter = nv->begin(); iter != nv->end(); ++iter)
// ans[iter->first] += iter->second;
// }
for(int i = 1; i <= n; ++i){
ll v = a[i];
int p = i, lp = i;
while(true){
p = lp;
for(int j = maxdep - 1; j >= 0; --j)
if(query(i, min(n, p + (1 << j) - 1)) == v && (p += 1 << j) > n)
break;
p = min(p, n + 1);
ans[v] += p - lp;
if(p > n)
break;
v = query(i, lp = p);
}
}
#ifdef BRUTEFORCE
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
ans[query(i, j)]--;
for(auto iter: ans)
if(iter.second != 0)
cerr << "WTH " << endl;
return 0;
#endif
rd(q);
while(q--){
ll x;
rd(x);
pd(ans[x]);
putchar('\n');
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 23ms
memory: 1376kb
input:
1071 546 2340 8190 420 6300 1050 40950 25 23400 195 2340 630 195 40950 2184 504 525 130 2340 1800 39...
output:
29 568770 132 197 63 84 197 63 1099 568770 29 164 22 113 197 84 1099 568770 197 197 568770 716 132 6...
result:
ok 253041 lines
Test #2:
score: 10
Accepted
time: 14ms
memory: 1640kb
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:
183 440 521 100 3619 1310 183 201 100 521 100 468 129 331 468 4128473 100 440 183 4128473 4128473 13...
result:
ok 278290 lines
Test #3:
score: 10
Accepted
time: 19ms
memory: 1464kb
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:
1412451 1545 220 47 925 1412451 1412451 925 90 330 220 196 90 815 94 92 90 1412451 92 248 815 248 81...
result:
ok 253539 lines
Test #4:
score: 10
Accepted
time: 29ms
memory: 1732kb
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:
1954 1954 1940 2980 165 565 165 135 538 2980 569 1954 6081994 2980 165 178 1954 569 422 569 1954 538...
result:
ok 278788 lines
Test #5:
score: 10
Accepted
time: 103ms
memory: 10708kb
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:
10574 1873 1873 10249 3685 3735 10249 2152307887 10249 10249 1873 7058 10261 3672 2152307887 10249 1...
result:
ok 288360 lines
Test #6:
score: 10
Accepted
time: 144ms
memory: 15560kb
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:
16046 2780 15425 51019 5415 16035 11219 11219 16046 5417 51019 16035 15425 16035 5417 5517 51019 278...
result:
ok 288858 lines
Test #7:
score: 10
Accepted
time: 58ms
memory: 4984kb
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:
13708 638 4405 4405 4175 4405 1333 4238 638 13173 4238 2712 1360 1333 4405 13173 4175 4405 2712 2712...
result:
ok 280460 lines
Test #8:
score: 10
Accepted
time: 77ms
memory: 7412kb
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:
6626 2410 7045 917526742 2410 2354 917526742 4904 2354 2456 917526742 917526742 7148 2354 7045 7148 ...
result:
ok 255709 lines
Test #9:
score: 10
Accepted
time: 111ms
memory: 12272kb
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:
12422 2922417371 12341 12121 8442 4236 38390 12422 4273 2030 4236 4155 41537 38390 2922417371 4236 8...
result:
ok 256207 lines
Test #10:
score: 10
Accepted
time: 61ms
memory: 15652kb
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