HUD—6287，口算训练，思维，素因子分解，lower_bound， upper_bound

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 6517    Accepted Submission(s): 1423

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n,m;
int a[N];
int l, r, d;
vector<int>G[N];
 
void F(int t, int index) {
	for (int i = 2; i * i <= t; i++) {
		while (t % i == 0) {
			G[i].push_back(index);
			t /= i;
		}
	}
	if (t>1) {
		G[t].push_back(index);
	}
}
 
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i < N; i++)G[i].clear();
		for (int i = 1,t; i <= n; i++) {
			scanf("%d", &t);
			F(t,i);
		}
		while (m--) {
			int flg = 0,cnt=0;
			scanf("%d%d%d", &l, &r, &d);
			for (int i = 2; i * i <= d; i++) {
				cnt = 0;
				while (d % i == 0) {
					d /= i;
					cnt++;
				}
				if (cnt) {//千万注意，不能少这个判断，否则会多出很多无意义的运行，回爆时间
					//lower_bound 返回一个迭代器，指向序列中不小于给定值的第一个元素。
					//upper_bound 返回一个迭代器，指向序列中大于给定值的第一个元素。
					int pp = upper_bound(G[i].begin(), G[i].end(), r) - lower_bound(G[i].begin(), G[i].end(), l);
					if (pp < cnt) {
						flg = 1;
						break;
					}
				}
			}
			if (d > 1) {
				int pp = upper_bound(G[d].begin(), G[d].end(), r) - lower_bound(G[d].begin(), G[d].end(), l);
				if (!pp) {
					flg = 1;
				}
			}
			if (flg) {
				printf("No\n");
			}
			else {
				printf("Yes\n");
			}
		}
	}
	return 0;
}