数学家的迷题_牛客博客

题意

有 $n(1 \le n \le 5*10^4)$ 个数 $a[i](1 \le a[i] \le 10^5)$

有两种操作

将 $a[id]$ 的值改为 $x$
给定区间 $[l,r]$ ，求出 $a[l] * a[l+1] * \dots * a[r-1] * a[r]$ 的不同的素数因子个数

思路

这里可以用线段树维护区间 $[l,r]$ 区间乘积可以被哪些素数整除

首先预处理出 $1e5$ 内的所有素数，方便查找素因子

维护数组 $mul[st][j]$ 表示第 $st$ 个节点表示的区间乘积可以被第 $j$ 个素数整除

显然如果使用数组区间操作时间复杂度很高，由于这里数组只有 $0$ 和 $1$ 两种情况，所以可以使用 $bitset$ 维护

Code

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
#define iss ios::sync_with_stdio(false)
#define debug(x) cout << #x << ": " << x << endl;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
#define ls st << 1
#define rs st << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
const int N = 5e4 + 5;
int a[N];
bitset<10005> mul[N << 2];//1~1e5内大约有1e4个素数
vector<ll> q;
bool vis[maxn];
void get_Prime() {
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) q.push_back(i);
        for (int j = 0; j < q.size(); ++j) {
            if (i * q[j] >= maxn) break;
            vis[i * q[j]] = true;
            if (i % q[j] == 0) break;
        }
    }
}
bitset<10005> calc(int x) {//将x的所有素因子找出
    bitset<10005> tmp;
    tmp.reset();//清空bitset
    for (int i = 0; x != 1 && q[i] * q[i] <= x ; ++i) {
        if (x % q[i] == 0) tmp.set(i);//如果存在该因数，第i位为1
        while (x % q[i] == 0) x /= q[i];
    }
    if(x != 1) tmp.set(lower_bound(q.begin(),q.end(),x)-q.begin());
    return tmp;
}
void push_up(int st) { mul[st] = mul[ls] | mul[rs]; }
void build(int st, int l, int r) {
    if (l == r) {
        mul[st] = calc(a[l]);
        return;
    }
    int mid = l + r >> 1;
    if (l <= mid) build(lson);
    if (mid < r) build(rson);
    push_up(st);
}
void updata(int st,int l,int r,int id,int x){
    if (l == r) {
        mul[st] = calc(x);
        return;
    }
    int mid = l + r >> 1;
    if (id <= mid) updata(lson,id,x);
    if (mid < id) updata(rson,id,x);
    push_up(st);
}
bitset<10005> query(int st,int l,int r,int L,int R){
    if(l >= L && r <= R){
        return mul[st];
    }
    int mid = l + r >> 1;
    bitset<10005> tmp;tmp.reset();
    if(mid >= L) tmp |= query(lson,L,R);
    if(mid < R) tmp |= query(rson,L,R);
    return tmp;
}
int main(){
    get_Prime();
    int n = read(),m = read();
    for(int i = 1 ; i <= n ; ++i) a[i] = read();
    build(1,1,n);
    while(m--){
        int op = read();
        if(op == 1){
            int id = read(),x = read();
            updata(1,1,n,id,x);
        }else{
            int l = read(),r = read();
            cout << query(1,1,n,l,r).count() << endl;//count()是bitset中为1的个数，在这里则指素因子的个数
        }
    }
}