HDU6287：口算训练（莫队算法）

Input第一行包含一个正整数 T(1≤T≤10)T(1≤T≤10)，表示测试数据的组数。 

每组数据第一行包含两个正整数 n,m(1≤n,m≤100000)n,m(1≤n,m≤100000)，分别表示序列长度以及问题个数。 

第二行包含 nn个正整数 a1,a2,...,an(1≤ai≤100000)a1,a2,...,an(1≤ai≤100000)，表示序列中的每个数。 

接下来 mm行，每行三个正整数 l,r,d(1≤l≤r≤n,1≤d≤100000)l,r,d(1≤l≤r≤n,1≤d≤100000)，表示每个问题。Output对于每个问题输出一行，若是倍数，输出Yes，否则输出No。Sample Input

1
5 4
6 4 7 2 5
1 2 24
1 3 18
2 5 17
3 5 35

Sample Output

Yes
No
No
Yes

思路：朴素的想法对N个数分解质因子分别维护前缀和，但是100000范围素数有点多时间不允许，容易发现每个数>sqrt(100000)的质因子至多有一个，那么单独处理这一个就行了，可以用莫队维护或者二分。

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+30;
int p[maxn], cnt=0, vis[maxn], tot[maxn]={0}, len;
int a[maxn], val[maxn], sum[maxn][66], id[maxn];
int ans[maxn];
inline void scan(int &ret)
{
    ret = 0;
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar();
}
void init()
{
    int up = (int)sqrt(100000);
    for(int i=2; i<=up; ++i)
    {
        if(vis[i] == 0)
        {
            p[++cnt] = i;
            id[i] = cnt;
            for(int j=i+i; j<=up; j+=i)
                vis[j] = 1;
        }
    }
}
struct node
{
    int l, r, id, fk, block;
    node(){}
    node(int l, int r, int fk, int id):l(l),r(r),fk(fk), id(id){block=l/len;}
    bool operator <(const node b) const
    {
        if(block == b.block) return r<b.r;
        return block<b.block;
    }
}q[maxn];
int main()
{
    init();
    int t, n, m;
    scanf("%d",&t);
    while(t--)
    {
        scan(n);
        scan(m);
        len = sqrt(m);
        memset(sum, 0, sizeof(sum));
        memset(tot, 0, sizeof(tot));
        for(int i=1; i<=n; ++i)
        {
            val[i] = 0;
            scan(a[i]);
            for(int j=1; p[j]<=a[i] && j<=cnt; ++j)
            {

                if(a[i]%p[j]==0)
                {
                    int res = 0;
                    while(a[i]%p[j]==0)
                    {
                        ++res;
                        a[i] /= p[j];
                    }
                    sum[i][id[p[j]]] += res;
                }
            }
            for(int j=1; j<=65; ++j) sum[i][j] += sum[i-1][j];
            if(a[i] != 1) val[i] = a[i];
        }
        int l, r, fk;
        for(int i=1; i<=m; ++i)
        {
            scan(l);
            scan(r);
            scan(fk);
            q[i] = node(l,r,fk,i);
        }
        sort(q+1,q+1+m);
        int L=1, R=1;
        if(val[1]) ++tot[val[1]];
        for(int i=1; i<=m; ++i)
        {
            int fk = q[i].fk, l= q[i].l, r=q[i].r, to = q[i].id;
            int flag = 1;
            for(int j=1; j<=cnt&&p[j]<=fk; ++j)
            {
                if(fk % p[j]==0)
                {
                    int res = 0;
                    while(fk%p[j]==0)
                    {
                        ++res;
                        fk /= p[j];
                    }
                    int idd = id[p[j]];
                    if(sum[r][idd]-sum[l-1][idd] < res)
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            while(R<r)
            {
                ++R;
                ++tot[val[R]];
            }
            while(L>l)
            {
                --L;
                ++tot[val[L]];
            }
            while(R>r)
            {
                --tot[val[R]];
                --R;
            }
            while(L<l)
            {
                --tot[val[L]];
                ++L;
            }
            if(fk != 1 && tot[fk]==0) flag = 0;
            ans[to] = flag;
        }
        for(int i=1; i<=m; ++i)
        {
            if(ans[i]) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}