Submission #66791

ソースコード

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

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
 
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;
            }
        }
    }
 
    map<int, int> query(int n){
        map<int, int> res;
        while(n > 1){
            res[min_factor[n]]++;
            n /= min_factor[n];
        }
        return (res);
    }
};
 
long long pow(int a, int b){
    long long ret = 1;
    for(int i = 0; i < b; ++i){
        ret *= a;
    }
    return (ret);
}
 
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);
            long long res = 1;
 
            for(auto [p, k] : pf.query(v)){
                res *= (pow(p, k + 1) - 1) / (p - 1);
            }
 
            cout << res << '\n';
        }
    }
 
    return (0);
}

ステータス

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

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01.txt	AC	74 ms	7388 KB	1
in02.txt	AC	52 ms	7132 KB	1
in03.txt	AC	108 ms	7256 KB	1
in04.txt	AC	71 ms	7360 KB	1
in05.txt	AC	100 ms	7608 KB	1
in06.txt	AC	58 ms	7560 KB	1
in07.txt	AC	98 ms	8004 KB	1
in08.txt	AC	88 ms	5704 KB	1
in09.txt	AC	91 ms	6864 KB	1
in10.txt	AC	61 ms	8036 KB	1
in11.txt	AC	44 ms	6360 KB	1
in12.txt	AC	58 ms	6228 KB	1
in13.txt	AC	100 ms	7288 KB	1
in14.txt	AC	57 ms	7648 KB	1
in15.txt	AC	56 ms	8944 KB	1
in16.txt	AC	47 ms	7732 KB	1
in17.txt	AC	74 ms	6648 KB	1
in18.txt	AC	52 ms	6952 KB	1
in19.txt	AC	114 ms	10112 KB	1
in20.txt	AC	123 ms	10612 KB	1
in21.txt	AC	147 ms	12260 KB	1
in22.txt	AC	108 ms	13020 KB	1
in23.txt	AC	123 ms	13776 KB	1
in24.txt	AC	100 ms	14532 KB	1
in25.txt	AC	95 ms	15292 KB	1
in26.txt	AC	99 ms	16048 KB	1
in27.txt	AC	105 ms	16672 KB	1
in28.txt	AC	110 ms	18064 KB	1
sample.txt	AC	21 ms	15236 KB	1