zoj_3886 Nico Number

题目:

  Kousaka Honoka and Minami Kotori are playing a game about a secret of Yazawa Nico.
  When the game starts, Kousaka Honoka will give Minami Kotori an array A of N non-negative integers. There is a special kind of number in the array, which is called NicoNico-number. We call a integer x is a NicoNico-number, if all integers(no more than x) that is coprime with x could form an Arithmetic Sequence.
  Then Minami Kotori will choose some consecutive part of the array A, wondering the number of NicoNico-number in this part. What's more, Kousaka Honoka sometimes modify the value of some consecutive elements in the array. Now it is your task to simulate this game!

思路:

  区间取模应该算是一个很套路的东西了,只要记录区间中最大值,然后暴力递归的复杂度就是 的了。而这样区间操作也变成了暴力修改每个数,所以只要能快速的判断每个数字是不是 问题就解决了。
  对于一个数字 ,如果 是一个奇数,那么 互质,根据等差数列的限制, 就要和所有小于 的数互质,因此 必须是质数
  而如果 是一个偶数且 不是 的倍数,那么 就得和所有奇数互质,因此 就必须能表示成
  如果 的倍数,设最小的与 互质的数为 ,如果 ,那 就不可能出现在等差数列中(因为 ),而 又和 互质,所以此时 不符合要求。如果 ,那么只要 项就会出现 的倍数,所以必须保证 , 满足要求的只有
  根据题目的意思 也是符合要求的。因为值域只有 ,只要预处理一下就能 判断了。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1e5 + 5;

bool mp[(int) 1e7 + 5], np[(int) 1e7 + 5];
int pri[(int) 1e7 + 5];
int getPrime(int n) {
    int tot = 0;
    rep(i, 2, n) {
        if(!np[i]) pri[++tot] = i;
        rep(j, 1, tot) {
            if(i * pri[j] > n) break;
            np[i * pri[j]] = true;
            if(i % pri[j] == 0) break;
        }
    }
    return tot;
}

int mx[N << 2], cnt[N << 2];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid (L + R >> 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
void build(int a[], int o, int L, int R) {
    if(L == R) {
        mx[o] = a[L];
        cnt[o] = mp[a[L]];
        return;
    }
    build(a, lson); build(a, rson);
    mx[o] = max(mx[ls], mx[rs]);
    cnt[o] = cnt[ls] + cnt[rs];
}
void mod(int l, int r, int p, int o, int L, int R) {
    if(mx[o] < p) return;
    if(L == R) {
        mx[o] %= p;
        cnt[o] = mp[mx[o]];
        return;
    }
    if(r <= mid) mod(l, r, p, lson);
    else if(l > mid) mod(l, r, p, rson);
    else mod(l, mid, p, lson), mod(mid + 1, r, p, rson);
    mx[o] = max(mx[ls], mx[rs]);
    cnt[o] = cnt[ls] + cnt[rs];
}
int qry(int l, int r, int o, int L, int R) {
    if(L == l && R == r) return cnt[o];
    if(r <= mid) return qry(l, r, lson);
    else if(l > mid) return qry(l, r, rson);
    else return qry(l, mid, lson) + qry(mid + 1, r, rson);
}
void upd(int x, int v, int o, int L, int R) {
    if(L == R) {
        mx[o] = v;
        cnt[o] = mp[v];
        return;
    }
    if(x <= mid) upd(x, v, lson);
    else upd(x, v, rson);
    mx[o] = max(mx[ls], mx[rs]);
    cnt[o] = cnt[ls] + cnt[rs];
}

int t[N];
int main() {
    // freopen("data.in", "r", stdin);
    int tot = getPrime(1e7), n, m, a, b, c, f;
    rep(i, 1, tot) mp[pri[i]] = true;
    rep(i, 0, 23) mp[1 << i] = true;
    mp[6] = mp[0] = true;
    while(~scanf("%d", &n)) {
        rep(i, 1, n) scanf("%d", t + i);
        build(t, 1, 1, n);
        scanf("%d", &m);
        while(m--) {
            scanf("%d%d%d", &f, &a, &b);
            if(f == 1) printf("%d\n", qry(a, b, 1, 1, n));
            else if(f == 2) {
                scanf("%d", &c);
                mod(a, b, c, 1, 1, n);
            }
            else upd(a, b, 1, 1, n);
        }
    }
    return 0;
}