口算训练 HDU - 6287
小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。
思路：我们肯定不能用暴力来求解，那样子结果肯定会T 所以我们经过仔细思考，我们可以用质因数分解来求解，因为一个数能被另一个数整除的话，那么结果肯定是d的质因子都在区间质因子出现并且个数大于等于d中每个质因子的个数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAX_N = 1e5 + 5;
static const ll Mod = 233;
static const int N = 105;
static const int INF = 0x3f3f3f3f;
vector<int>vec[MAX_N];
void pre_deal(int x, int ind) { //预处理存储因子对应序列编号
for (int i = 2; i * i <= x; ++i) {
while (x % i == 0) {
vec[i].push_back(ind);
x /= i;
}
}
if (x > 1) vec[x].push_back(ind);
}
int get_div(int l, int r, int i) { //r到l中因子i的数量
return upper_bound(vec[i].begin(), vec[i].end(), r) - upper_bound(vec[i].begin(), vec[i].end(), l - 1);
}
bool solve(int l, int r, int d) {
for (int i = 2; i * i <= d; ++i) {
int cnt = 0;
while (d % i == 0) {
cnt++;
d /= i;
}
if (cnt > get_div(l, r, i)) return false;
}
//存在不可分解的因子，特判
if (d > 1 && get_div(l, r, d) <= 0) return false;
return true;
}
int main() {
/*freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);*/
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < MAX_N; ++i) vec[i].clear();
for (int i = 1; i <= n; ++i) {
int v;
scanf("%d", &v);
pre_deal(v, i);
}
while (m--) {
int l, r, d;
scanf("%d%d%d", &l, &r, &d);
if (solve(l, r, d)) puts("Yes");
else puts("No");
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读