首页 > 试题广场 >

最大GCD

[编程题]最大GCD

给出长度为n的序列，序列中有个元素，你需要进行次查询，每次查询形如以下格式：

         ：你需要选择两个整数满足，使得最大化。


输入描述:
第一行两个整数
第二行n个整数
接下来行每行三个整数表示一个查询


输出描述:
对于每个查询输出一个整数表示的最大值。
示例1

输入

4 2
2 4 3 6
1 3 6
1 4 10

输出

3
2

备注:
算法知识视频讲解
开通博客
头像 num73
发表于 2020-03-01 20:30:33
由最大公因数的性质:且，易得到结论：对于每一个询问，我们只需在到这个区间中找到一个，使得对任意的成立。 算法1先考虑最朴素的做法：对于每一次询问，求出到这个区间中的每一个数与的最大公因数，并记录最大的那一个。时间复杂度(为最大值)，很显然，对于本题的数据规模这个复杂度是不够的。 观察这个题的特点 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 看见我请叫我去学习HA
发表于 2020-03-01 20:16:43
题意：Face 数据范围 Strategy: 看到数据范围可以想到先把1e5以内的因子全部筛一遍, 不要问我为什么比赛的时候没想到,,, 然后pos[i]存i作为因子出现在那些数的下标, 然后每次询问从x的最大因子开始往下走, 询问pos[x_因子]有没有在区间[l, r]中出现过 服了不晓得为啥 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
0条回答 2浏览

热门推荐

相关试题

最大GCD

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号