Submission #67999

ソースコード

?
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
#include <bits/stdc++.h>
#include <iostream>
#define lol long long
#define gcd(x, y) __gcd(x, y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed(x) fixed << setprecision(x)
#define all(x) x.begin(),x.end()
using namespace std;
using pii = pair<int, int>;
template <class A, class B>
inline bool chmax(A& a, const B& b) {
return b > a && (a = b, true);
}
template <class A, class B>
inline bool chmin(A& a, const B& b) {
return b < a && (a = b, true);
}
template <class A>
inline A abs(A& a) {
return (a < 0 ? -a : a);
}
bool inLine(int x, int y, int mx, int my) {
return (x >= 0 && y >= 0 && x < mx && y < my);
}
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<class T> using uset=unordered_set<T>;
template<class A,class B> using umap=unordered_map<A,B>;
const lol inf = (1LL << 62);
const int MOD = (1e9) + 7;
const int mod = 998244353;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1, -2, -2, -2, -2,
-2, -1, -1, 1, 1, 0, 0, 2, 2, 2, 2, 2};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1, -2, -1, 0, 1,
2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2};
template <typename X>
struct Segment{
using FX=function<X(X,X)>; //X●X -> X となる関数の型
int n;
FX fx;
const X ex;
vector<X> dat;
Segment(int size,FX fx_,X ex_) : fx(fx_),ex(ex_){
n=1;
while(size>n){
n <<=1;
}
dat.resize(n*2,ex_);
return;
}
void set(int i,X x){ dat[i+n-1]=x;}
void build(){
for(int k=n-2;k>=0;k--) dat[k]=fx(dat[2*k+1],dat[2*k+2]);
return;
}
void update(int i,X x){
i+=n-1;
dat[i]=x;
while(i>0){
i=(i-1)/2;
dat[i]=fx(dat[i*2+1],dat[i*2+2]);
}
return;
}
X get(int a,int b){ return (get_sub(a,b+1,0,0,n));}
X get_sub(int a,int b,int k,int l,int r){
if(r<=a || b<=l) return ex;
if(a<=l && r<=b) return dat[k];
X vl=get_sub(a,b,k*2+1,l,(l+r)/2);
X vr=get_sub(a,b,k*2+2,(l+r)/2,r);
return fx(vl,vr);
}
X operator[](const int &k) const{
return dat[k+n-1];
}
X find_rightest(int a, int b, X x) { return find_rightest_sub(a, b, x, 0, 0, n); }
X find_leftest(int a, int b, X x) { return find_leftest_sub(a, b, x, 0, 0, n); }
X find_rightest_sub(int a, int b, X x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外
return a - 1;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn
return vr;
} else { // 左の部分木を見て値をreturn
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
X find_leftest_sub(int a, int b, X x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外
return b;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // 左の部分木を見て b 以外ならreturn
return vl;
} else { // 右の部分木を見て値をreturn
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
};
std::vector<int> sieve(int n) {
std::vector<int> res(n+1);
std::iota(res.begin(), res.end(), 0);
for (int i = 2; i*i <= n; ++i) {
if (res[i] < i) continue;
for (int j = i*i; j <= n; j += i)
if (res[j] == j) res[j] = i;
}
return res;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
auto sie = sieve(1000000);
int N,Q;
cin >>N>>Q;
Segment<int> st(N, [](int x1,int x2) -> int {return gcd(x1,x2);}, 0);
for(int i=0;i<N;i++){
int a;
cin >>a;
st.set(i, a);
}
st.build();
for(int i=0;i<Q;i++){
int t,x,y;
cin >>t>>x>>y;
if(t==1){
st.update(x-1, y);
}else{
lol ans = 1;
map<int,int> yaku;
auto tmp = st.get(x-1,y-1);
while(tmp > 1){
yaku[sie[tmp]]++;
tmp /= sie[tmp];
}
for(auto&& p:yaku){
lol sum=1,tmp2=1;
for(int j=0;j<p.se;j++){
tmp2 *= p.fi;
sum += tmp2;
}
ans *= sum;
}
cout <<ans<<'\n';
}
}
return (0);
}

ステータス

項目 データ
問題 1516 - 『公約数』総和企画
ユーザー名 ei1923
投稿日時 2021-08-05 10:05:56
言語 C++17
状態 Accepted
得点 5
ソースコード長 4820 Byte
最大実行時間 184 ms
最大メモリ使用量 17292 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 75 ms 6620 KB
1
in02.txt AC 44 ms 6496 KB
1
in03.txt AC 125 ms 6760 KB
1
in04.txt AC 91 ms 6896 KB
1
in05.txt AC 130 ms 7024 KB
1
in06.txt AC 67 ms 7148 KB
1
in07.txt AC 123 ms 7408 KB
1
in08.txt AC 103 ms 5620 KB
1
in09.txt AC 86 ms 6524 KB
1
in10.txt AC 60 ms 7684 KB
1
in11.txt AC 46 ms 6156 KB
1
in12.txt AC 66 ms 6032 KB
1
in13.txt AC 101 ms 7060 KB
1
in14.txt AC 63 ms 7192 KB
1
in15.txt AC 57 ms 8352 KB
1
in16.txt AC 50 ms 7332 KB
1
in17.txt AC 86 ms 6568 KB
1
in18.txt AC 70 ms 6892 KB
1
in19.txt AC 163 ms 9456 KB
1
in20.txt AC 163 ms 9844 KB
1
in21.txt AC 184 ms 11380 KB
1
in22.txt AC 129 ms 12156 KB
1
in23.txt AC 141 ms 12920 KB
1
in24.txt AC 130 ms 13696 KB
1
in25.txt AC 133 ms 14472 KB
1
in26.txt AC 129 ms 15236 KB
1
in27.txt AC 117 ms 15880 KB
1
in28.txt AC 158 ms 17292 KB
1
sample.txt AC 31 ms 15244 KB
1