UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215234#2643. gcdN100639ms15652kbC++113.0kb2024-11-27 19:30:222024-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