后几页有我会做的题……很好，我很安详，，，

考虑将所有数质因数分解。那么询问\([l, r]\)中所有数的积是否是\(d\)的倍数的本质就是对于\(d\)的每一类质因子，询问区间中该类质因子的指数之和是否不小于\(d\)中的。

考虑到数的范围都很小（不超过100000），我们可以先线性筛预处理，这样一次分解质因数的复杂度就降为了\(O(\log n)\)。至于维护区间每类质因子的指数和这种事……就用主席树处理吧。

代码：

/**************************************************************
    Problem: 5358
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2804 ms
    Memory:68408 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
const int maxn = 100005;
int minp[maxn], mint[maxn], minh[maxn];
int prm[maxn], pcnt;
bool vis[maxn];
void sieve() {
  const int N = 100000;
  vis[1] = true; pcnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[++ pcnt] = i;
      minp[i] = pcnt; mint[i] = 1;
      minh[i] = i;
    }
    for(int j = 1; j <= pcnt && i * prm[j] <= N; j ++) {
      int v = i * prm[j];
      vis[v] = true; minp[v] = j;
      if(i % prm[j] == 0) {
        mint[v] = mint[i] + 1; minh[v] = minh[i] * prm[j];
        break;
      } else {
        mint[v] = 1; minh[v] = prm[j];
      }
    }
  }
}
 
const int bufsiz = 64 * 1024 * 1024;
char buf[bufsiz]; char *cur;
void init_buf() {
  cur = buf;
}
void *alloc(size_t size) {
  if(cur + size - buf > bufsiz) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}
 
struct Node {
  int v; Node *lc, *rc;
};
Node *build_tree(int L, int R) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> v = 0; 
  if(L == R) {
    ret -> lc = ret -> rc = NULL;
  } else {
    int M = (L + R) / 2;
    ret -> lc = build_tree(L, M);
    ret -> rc = build_tree(M + 1, R);
  }
  return ret;
}
Node *add_p(Node *o, int L, int R, int p, int v) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> v = o -> v;
  ret -> lc = o -> lc; ret -> rc = o -> rc;
  if(L == R) {
    ret -> v += v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      ret -> lc = add_p(ret -> lc, L, M, p, v);
    } else {
      ret -> rc = add_p(ret -> rc, M + 1, R, p, v);
    }
  }
  return ret;
}
int query(Node *o, int L, int R, int p) {
  if(L == R) {
    return o -> v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      return query(o -> lc, L, M, p);
    } else {
      return query(o -> rc, M + 1, R, p);
    }
  }
}
 
Node *rt[maxn];
void solve() {
  init_buf();
  int n, m; scanf("%d%d", &n, &m);
  rt[0] = build_tree(1, pcnt);
  for(int i = 1; i <= n; i ++) {
    rt[i] = rt[i - 1];
    int x; scanf("%d", &x);
    while(x > 1) {
      int p = minp[x], t = mint[x];
      rt[i] = add_p(rt[i], 1, pcnt, p, t);
      x /= minh[x];
    }
  }
  while(m --) {
    int l, r, d; scanf("%d%d%d", &l, &r, &d);
    bool ok = true;
    while(d > 1) {
      int p = minp[d], t = mint[d];
      int st = query(rt[r], 1, pcnt, p) - query(rt[l - 1], 1, pcnt, p);
      if(st < t) {
        ok = false; break;
      }
      d /= minh[d];
    }
    if(ok) {
      puts("Yes");
    } else {
      puts("No");
    }
  }
}
 
int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    solve();
  }
  return 0;
}

• 相关文章
• 全局相关文章