题意：
小Q非常喜欢数学，但是他的口算能力非常弱。因此他找到了小T，给了小T一个长度为nn的正整数序列a1,a2,...,ana1,a2,...,an，要求小T抛出mm个问题以训练他的口算能力。
每个问题给出三个正整数l,r,dl,r,d，小Q需要通过口算快速判断al×al+1×...×ar−1×aral×al+1×...×ar−1×ar是不是dd的倍数。
小Q迅速地回答了出来，但是小T并不知道正确答案是什么，请写一个程序帮助小T计算这些问题的正确答案。
思路：
一开始bit套map 用前缀和处理，tle了？
对于每一个输入的数字，分解质因子，对于每一个质因子，把这个数字的位置push到这个质因子的vector里面去。
那么每一个vector里面的数字就是非递减的了。
然后对于每一个输入的l，r，d，把d分解质因子，对于每一个质因子，在这个质因子的vector里面找第一个大于等于l的位置和最后一个小于等于r的位置，相减，比较是否有d中这个质因子的数量多。
找的时候当然利用前面的非递减，所以可以二分。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + ; vector<int> p;
vector<int> G[N],g[N];
bool pp[N];
int a[N];
int n,m; int main()
{
for (int i = ;i < N;i++)
{
if (!pp[i])
{
p.push_back(i);
for (int j = i * ;j < N;j += i)
{
G[j].push_back(i);
pp[j] = ;
}
}
}
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
for (int i = ;i < p.size();i++)
{
g[p[i]].clear();
}
for (int i = ;i <= n;i++)
{
int x;
scanf("%d",&x);
if (x == ) continue;
if (!pp[x])
{
g[x].push_back(i);
continue;
}
for (int j = ;j < G[x].size();j++)
{
int cnt = ;
int tmp = x;
int v = G[x][j];
while (tmp % v == )
{
tmp /= v;
g[v].push_back(i);
}
}
}
while (m--)
{
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
if (d == )
{
puts("Yes");
continue;
}
if (!pp[d])
{
int x = lower_bound(g[d].begin(),g[d].end(),l) - g[d].begin();
int y = upper_bound(g[d].begin(),g[d].end(),r) - g[d].begin();
y--;
if (y - x + < ) puts("No");
else puts("Yes");
}
else
{
bool f = ;
for (int i = ;i < G[d].size();i++)
{
int v = G[d][i];
int cnt = ;
int tmp = d;
while (tmp % v == )
{
cnt++;
tmp /= v;
}
int x = lower_bound(g[v].begin(),g[v].end(),l) - g[v].begin();
int y = upper_bound(g[v].begin(),g[v].end(),r) - g[v].begin();
y--;
if (y - x + < cnt) f = ;
if (f) break;
}
if (f) puts("No");
else puts("Yes");
}
}
}
return ;
}