专栏首页ypw口算训练 HDU - 6287

口算训练 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 回溯法求组合问题

    用户7727433
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    用户7727433
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433
  • 一遍记住Java常用的八种排序算法与代码实现

    对Java技术,架构技术感兴趣的同学,欢迎加QQ群668041364,一起学习,相互讨论。 群内已经有小伙伴将知识体系整理好(源码,笔记,PPT,学习视频),欢...

    java爱好者
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • LeetCode 164. Maximum Gap (排序)

    题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率...

    ShenduCC
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768

扫码关注云+社区

领取腾讯云代金券