「校内训练2019-08-24」数数

Description

给你一个序列长度为$n$的序列$a$,每次进行以下两种操作:

  • 1 p y,将$a[p]$变成$y$。
  • 2 l r y,查询区间$[l,r]$内,$a[i]$和$y$互质的个数。

Data Range

$0\leq n,m\leq 5\times 10^4,a[i],y\leq 10^5$

Solution

按照套路,互质可以理解为两个数不存在相同的质因子。

因为数据范围不是特别大,考虑对值域质因子分解后可得,在$[1,10^5]$的范围内,一共有不到$10^4$个质数。

考虑暴力分块,对于每一个块内,我们维护若干个bitset表示这个块内所有数,若干个表示的是质因子的个数。按照位置,$0$表示第$i$位所代表的$a[i]$没有$y$的某一个质因子,$1$表示存在这个质因子。

每一次修改,就先删除某一个点对应的所有质因子,然后修改$a[pos]$,然后暴力重构这一个块,单次修改的复杂度为$O({\sqrt n}^2)$,不过跑不满。

每一次查询,我们考虑计算出和$y$互质的数,然后用总个数减去。在相邻的块和边角暴力不做赘述。

那么考虑整块的暴力,我们就用bitset来按位或所有$y$质因子出现的位置,这样可以不用考虑容斥,那么$1$的个数就是不互质的个数。

Code

#include <bits/stdc++.h>
#define block_st(x) ((x - 1) * block_len + 1)
#define block_ed(x) (x * block_len)
#define REP(i, s, t) for (int i = (s), i##ed = (t); i <= i##ed; ++ i)
using namespace std;
template <typename T> void read(T &x) {
  x = 0; char ch = 0; bool flg = 0; for (; !isdigit(ch); ch = getchar()) flg |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48); flg ? x *= -1 : 233;
}
template <typename T> void write(T x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T> T gcd(T x, T y) { return !y ? x : gcd(y, x % y); }
int prime_cnt;
int nxt[100005], prime[10005], pid[100005];
bool nt_prime[100005];
void get_prime(int n) {
  memset(nxt, 0, sizeof nxt); 
  REP(i, 2, n) {
    if (!nt_prime[i]) {
      prime[++ prime_cnt] = i, pid[i] = prime_cnt;
      for (int j = 2; j * i <= n; ++ j) {
        nt_prime[i * j] = 1; nxt[i * j] = i; 
      }
    }
  }
}
namespace _divide {
  int q[325], tot, y; 
  void _div(int x) {
    tot = 0; 
    while (nxt[x]) {
      q[++ tot] = nxt[x]; y = x; 
      while (!(x % nxt[y])) x /= nxt[y]; 
    }
    if (x != 1) q[++ tot] = x; 
  }
}
int block_len, n, Q;
int bel[50005], a[100005];
bitset<250> blo[9600][250], tmp;
void insert(int pos, int _val) {
  int dig = pos - block_st(bel[pos]);
  _divide::_div(_val);
  REP(i, 1, _divide::tot) blo[pid[_divide::q[i]]][bel[pos]].set(dig); 
}
int solve(int l, int r, int d) {
  int res = 0; 
  if (bel[l] + 1 >= bel[r]) {
    REP(i, l, r) if (gcd(d, a[i]) != 1) ++ res;
    return res;
  }
  _divide::_div(d);
  REP(i, l, block_ed(bel[l])) if (gcd(a[i], d) != 1) ++ res;
  REP(i, block_st(bel[r]), r) if (gcd(a[i], d) != 1) ++ res;
  REP(i, bel[l] + 1, bel[r] - 1) {
    tmp.reset(); 
    REP(j, 1, _divide::tot) tmp |= blo[pid[_divide::q[j]]][i]; 
    res += tmp.count(); 
  }
  return res;
}
void modify(int pos, int _val) {
  _divide::_div(a[pos]);
  int block_st = (bel[pos] - 1) * block_len + 1; 
  REP(i, 1, _divide::tot) blo[pid[_divide::q[i]]][bel[pos]].reset();
  a[pos] = _val;
  REP(i, block_st(bel[pos]), block_ed(bel[pos])) {
    _divide::_div(a[i]);
    REP(j, 1, _divide::tot) blo[pid[_divide::q[j]]][bel[pos]].set(i - block_st(bel[pos]));
  }
}
int main() {
  get_prime(100000); 
  read(n); block_len = sqrt(n);
  REP(i, 1, n) bel[i] = (i - 1) / block_len + 1;
  REP(i, 1, n) read(a[i]), insert(i, a[i]); 
  read(Q); int opt, x, y, z; 
  REP(iq, 1, Q) {
    read(opt); 
    if (opt == 1) { read(x); read(y); modify(x, y); }
    else { read(x); read(y); read(z); write(y - x + 1 - solve(x, y, z)); puts(""); }
  }
  return 0; 
}
最后修改:2019 年 08 月 24 日 09 : 24 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论