[BZOJ5358]/[HDU6287]口算训练

题目大意：

给定一个长度为\(n(n\le10^5)\)的正整数序列\(a_{1\sim n}\)，\(m(m\le10^5)\)次询问。每次询问给出三个正整数\(l,r,d\)，判断\(\displaystyle\prod_{i=l}^ra_i\)是不是\(d\)的倍数。

思路：

线性筛预处理出\(10^5\)内的所有素数。对于\(a\)中每一个数分解质因数，并开vector存储每个质因子出现的位置（如在同一个位置出现多次则算作多次）。对于每次询问的\(d\)分解质因数，对于每个质因子在vector中二分其在区间内出现的次数，判断是否比\(d\)中的多即可。

时间复杂度\(\mathcal O(n(\sqrt n+\log^2n))\)。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=1e5+1,P=9593;int p[P],pos[N];bool vis[N];std::vector
        
          v[P];inline void sieve() {    vis[1]=true;    for(register int i=2;i