Submission #66788

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
template< typename Monoid, typename F >
struct SegmentTree {
int sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[a]);
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
template< typename Monoid, typename F >
SegmentTree< Monoid, F > get_segment_tree(int N, const F& f, const Monoid& M1) {
return {N, f, M1};
}
struct FastPrimeFactorization{
vector<int> min_factor;
FastPrimeFactorization(int n) : min_factor(n + 1){
iota(min_factor.begin(), min_factor.end(), 0);
for(int i = 2; i * i <= n; ++i){
if(min_factor[i] < i) continue;
for(int j = i * i; j <= n; j += i){
if(min_factor[j] == j) min_factor[j] = i;
}
}
}
vector<int> query(int n){
vector<int> res;
while(n > 1){
res.emplace_back(min_factor[n]);
n /= min_factor[n];
}
return (res);
}
};
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
FastPrimeFactorization pf(1e6);
auto seg = get_segment_tree(n, [](int a, int b){ return (gcd(a, b)); }, 0);
for(int i = 0; i < n; ++i){
seg.set(i, a[i]);
}
seg.build();
for(int i = 0; i < q; ++i){
int t, x, y;
cin >> t >> x >> y;
--x;
if(t == 1){
seg.update(x, y);
}else{
int v = seg.query(x, y);
vector<pair<int, int> > cnt;
for(auto p : pf.query(v)){
if(cnt.empty() || cnt.back().first != p){
cnt.emplace_back(p, 1);
}else{
cnt.back().second++;
}
}
long long res = 1;
for(auto [p, k] : cnt){
long long pow = 1;
for(int j = 0; j <= k; ++j){
pow *= p;
}
res *= (pow - 1) / (p - 1);
}
cout << res << '\n';
}
}
return (0);
}

ステータス

項目 データ
問題 1516 - 『公約数』総和企画
ユーザー名 ei1903
投稿日時 2021-06-01 14:43:03
言語 C++17
状態 Accepted
得点 5
ソースコード長 4577 Byte
最大実行時間 263 ms
最大メモリ使用量 97424 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 86 ms 9692 KB
1
in02.txt AC 98 ms 10712 KB
1
in03.txt AC 112 ms 14292 KB
1
in04.txt AC 79 ms 16700 KB
1
in05.txt AC 126 ms 20924 KB
1
in06.txt AC 64 ms 22672 KB
1
in07.txt AC 115 ms 26440 KB
1
in08.txt AC 104 ms 26828 KB
1
in09.txt AC 93 ms 30164 KB
1
in10.txt AC 70 ms 33124 KB
1
in11.txt AC 45 ms 31956 KB
1
in12.txt AC 62 ms 33096 KB
1
in13.txt AC 94 ms 36844 KB
1
in14.txt AC 91 ms 38868 KB
1
in15.txt AC 54 ms 41448 KB
1
in16.txt AC 48 ms 41256 KB
1
in17.txt AC 84 ms 41708 KB
1
in18.txt AC 58 ms 42916 KB
1
in19.txt AC 139 ms 50172 KB
1
in20.txt AC 263 ms 54508 KB
1
in21.txt AC 164 ms 60644 KB
1
in22.txt AC 139 ms 66136 KB
1
in23.txt AC 124 ms 71244 KB
1
in24.txt AC 125 ms 76356 KB
1
in25.txt AC 111 ms 81588 KB
1
in26.txt AC 132 ms 86692 KB
1
in27.txt AC 124 ms 91800 KB
1
in28.txt AC 124 ms 97424 KB
1
sample.txt AC 28 ms 94596 KB
1