“美登杯”上海市高校大学生程序设计邀请赛 （华东理工大学）E. 小花梨的数组_给定一个 nn 个数的数组, mm 次操作,每次操作为下列操作之一。求最后的数组。 操

题意：

给定一个长度为 $n$ 的数组 $a$，有 $m$ 次操作，① $1,l,r$，令区间所有 $a_i$ 乘上其最小质因子，若 $a_i$ 是 $1$ 则无视；② $2,l,r$，令区间所有 $a_i$ 除以其最小质因子；③ $3,x$，询问 $a_x$ 的值，模 $1e9+7$。$(n,m\le 10^5,a_i\le 10^6)$

链接：

https://acm.ecnu.edu.cn/contest/173/problem/E/

解题思路：

乘除法操作转化到因子的加减法上来，注意到每个数质因子个数不会很多，$10^6$ 以内的数，至多有 $7$ 个质因子。对于区间乘法，只需要打上加法标记即可；对于区间除法，如果不会使区间内的数的最小质因子改变的话，那么仍然可以直接打上加法标记，否则暴力 $dfs$ 到叶结点修改最小质因子，暴力访问叶结点这个过程至多进行 $7n$ 次，复杂度 $O(7nlogn)$，那么线段树上的总复杂度为 $O(mlogn+7nlogn)$。此外还有预处理质因子的复杂度，这题直接 $O(n\sqrt{a})$ 就够了。

参考代码：

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sz(a) ((int)a.size())
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

vector<pii> fac[maxn];
int a[maxn];
int n, m;

ll qpow(ll a, ll b){

    ll ret = 1;
    while(b){

        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

struct SegTree{

    int mn[maxn << 2], add[maxn << 2];
    void pushUp(int rt){

        mn[rt] = min(mn[lson], mn[rson]);
    }
    void build(int l, int r, int rt){

        if(l == r){

            mn[rt] = fac[l].back().second;
            return;
        }
        int mid = gmid;
        build(l, mid, lson);
        build(mid + 1, r, rson);
        pushUp(rt);
    }
    void pushDown(int rt){

        if(add[rt]){

            add[lson] += add[rt], add[rson] += add[rt];
            mn[lson] += add[rt], mn[rson] += add[rt];
            add[rt] = 0;
        }
    }
    void update(int l, int r, int rt, int L, int R, int val){

        if(l >= L && r <= R && mn[rt] + val > 0 || l == r){

            if(mn[rt] + val > 0) mn[rt] += val, add[rt] += val;
            else{

                fac[l].pop_back();
                mn[rt] = fac[l].back().second;
            }
            return;
        }
        int mid = gmid;
        pushDown(rt);
        if(L <= mid) update(l, mid, lson, L, R, val);
        if(R > mid) update(mid + 1, r, rson, L, R, val);
        pushUp(rt);
    }
    ll query(int l, int r, int rt, int pos){

        if(l == r){

            ll ret = 1;
            fac[l].back().second = mn[rt];
            for(auto &it : fac[l]) if(it.first != 1) ret = ret * qpow(it.first, it.second) % mod;
            return ret;
        }
        int mid = gmid;
        pushDown(rt);
        if(pos <= mid) return query(l, mid, lson, pos);
        else return query(mid + 1, r, rson, pos);
    }
} tr;

int main(){

    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){

        cin >> a[i];
    }
    for(int i = 1; i <= n; ++i){

        for(int j = 2; j * j <= a[i]; ++j){

            if(a[i] % j) continue;
            int cnt = 0;
            while(a[i] % j == 0) a[i] /= j, ++cnt;
            fac[i].pb({j, cnt});
        }
        if(a[i] > 1) fac[i].pb({a[i], 1});
        fac[i].pb({1, inf});
        reverse(fac[i].begin(), fac[i].end());
    }
    tr.build(1, n, 1);
    while(m--){

        int opt, x, y; cin >> opt >> x;
        if(opt == 1){

            cin >> y;
            tr.update(1, n, 1, x, y, 1);
        }
        else if(opt == 2){

            cin >> y;
            tr.update(1, n, 1, x, y, -1);
        }
        else{

            int ret = tr.query(1, n, 1, x);
            cout << ret << "\n";
        }
    }
    return 0;
}
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