Description:
小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。
每个问题给出三个正整数l,r,d,小Q需要通过口算快速判断al×al+1×…×ar−1×ar是不是d的倍数。
小Q迅速地回答了出来,但是小T并不知道正确答案是什么,请写一个程序帮助小T计算这些问题的正确答案。
Input:
第一行包含一个正整数T(1≤T≤10),表示测试数据的组数。
每组数据第一行包含两个正整数n,m(1≤n,m≤100000),分别表示序列长度以及问题个数。
第二行包含n个正整数a1,a2,…,an(1≤ai≤100000),表示序列中的每个数。
接下来m行,每行三个正整数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
题目链接
将输入的每个a数组分解质因数、记录,对d分解质因数判断a数组是否有足够的因数能够相乘满足成为输入d的倍数。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
}
int t;
int n, m;
vector<int> G[maxn];
int query(int l, int r, int x) {
return upper_bound(G[x].begin(), G[x].end(), r) - lower_bound(G[x].begin(), G[x].end(), l);
}
bool solve(int l, int r, int d) {
for (int i = 2; i * i <= d; ++i) {
if (d % i == 0) {
int cnt = 0;
while (d % i == 0) {
cnt++;
d /= i;
}
if (cnt > query(l, r, i)) {
return 0;
}
}
}
if (d > 1) {
if (query(l, r, d) < 1) {
return 0;
}
}
return 1;
}
int main(){
//fre();
scanf("%d", &t);
for (int Case = 1; Case <= t; ++Case) {
if (Case != 1) {
for (int i = 0; i < maxn; ++i) {
G[i].clear();
}
}
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
for (int j = 2; j * j <= x; ++j) {
while (x % j == 0) {
x /= j;
G[j].pb(i);
}
}
if (x > 1) {
G[x].pb(i);
}
}
while (m--) {
int l, r, d;
scanf("%d%d%d", &l, &r, &d);
puts(solve(l, r, d) ? "Yes" : "No");
}
}
return 0;
}