Submission #66790

ソースコード

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

187

188

#include <iostream>
#include <vector>
#include <numeric>
 
using namespace std;
 
#define int int64_t
 
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);
    }
};
 
signed 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:58:16
言語	C++17
状態	Accepted
得点	5
ソースコード長	4603 Byte
最大実行時間	193 ms
最大メモリ使用量	22772 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01.txt	AC	80 ms	12124 KB	1
in02.txt	AC	50 ms	11800 KB	1
in03.txt	AC	123 ms	11716 KB	1
in04.txt	AC	90 ms	11712 KB	1
in05.txt	AC	128 ms	12024 KB	1
in06.txt	AC	73 ms	12116 KB	1
in07.txt	AC	122 ms	12672 KB	1
in08.txt	AC	124 ms	9788 KB	1
in09.txt	AC	98 ms	11140 KB	1
in10.txt	AC	65 ms	12520 KB	1
in11.txt	AC	55 ms	10376 KB	1
in12.txt	AC	71 ms	10168 KB	1
in13.txt	AC	101 ms	11576 KB	1
in14.txt	AC	61 ms	11964 KB	1
in15.txt	AC	54 ms	13328 KB	1
in16.txt	AC	44 ms	12108 KB	1
in17.txt	AC	72 ms	10636 KB	1
in18.txt	AC	62 ms	10980 KB	1
in19.txt	AC	140 ms	14920 KB	1
in20.txt	AC	145 ms	15340 KB	1
in21.txt	AC	193 ms	16908 KB	1
in22.txt	AC	147 ms	17708 KB	1
in23.txt	AC	145 ms	18504 KB	1
in24.txt	AC	121 ms	19304 KB	1
in25.txt	AC	129 ms	20108 KB	1
in26.txt	AC	134 ms	20784 KB	1
in27.txt	AC	129 ms	21460 KB	1
in28.txt	AC	128 ms	22772 KB	1
sample.txt	AC	23 ms	19096 KB	1