首页 > 试题广场 >

能被多个质数整除的第K长子段

[编程题]能被多个质数整除的第K长子段

热度指数：286 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个正整数数组A和一个正整数X，设A的长度为N，数组中的元素依次为A[0]~A[N - 1]。
牛牛要挑选出符合以下条件的所有整数对(l, r)：
1、 $0 \leq l \leq r \leq N - 1$
2、存在至少X个不同的质数，每个质数都可以整除A[l]~A[r]之间的每一个数(A[l], A[l + 1], A[l + 2], ... A[r])。

现在定义一个整数对(l, r)的长度为r - l + 1，牛牛希望知道所有符合条件的整数对中，长度第K大的整数对长度是多少。

如果符合条件的数对不足K个，那么返回-1

示例1

输入

[2, 2],1,2

输出

说明

有三个合法的数对(0, 0), (0, 1), (1, 1)，长度分别为1, 2, 1，第2大的长度是1

备注:

算法知识视频讲解

摸鱼学大师

发表于 2021-08-10 15:05:28

精华题解思路：题目的主要信息：从~中挑选,作为区间，其中，即边界点可以重合如果存在至少个不同的质数，每个质数都可以整除~之间的每一个数我们要找到第k长的这样的区间，返回其长度即方法一：暴力法具体做法：根据题意，首先我们准备了2到数组最大值中的所有质数，记录到primes中。然后我们暴力遍历每一展开全文

诗云panther

发表于 2021-08-11 10:42:49

class Solution {public: static bool comp(pair<int, int>& a, pair<int, int>& b){ //重载比较，按区间大小排序 return a.second - a.first 展开全文

Maokt

发表于 2021-09-10 23:38:14

算法思想一：暴力法解题思路：根据题意： 1、首先我们准备了2到数组最大值中的所有质数，记录到primes中。 2、然后暴力遍历每一个数对，每次对于数对区间中的元素，对每一个primes中的质数，查看是否能整除区间中所有的元素，如果可以计数加1，当计数不小于时，就可以记录这展开全文

棒棒糖🍭201906101800876

发表于 2021-10-13 16:06:20

NC542 能被多个质数整除的第K长子段题目描述给你一个数组AAA和正整数X，KX，KX，K，定义如下的连续子序列A[l...r]A[l...r]A[l...r]是好的：存在至少X个不同的质数，可以整除子数组里的每个数求数组A所有的好的子序列里，第KKK长的是多长？ 1. 暴力直接根据题意展开全文

martin0621

发表于 2021-08-20 16:29:09

注意到，如果对于给定的区间左边界l，若满足题目条件的区间右边界最大为r，那么显然(l,r)的任意子区间也是满足条件的，也即固定区间左边界为(l,r)中任取的i，区间右边界至少为r。因此不需要记录每一个满足条件的区间对(i,j)再进行排序，而只需要对于左边界l从0到n-1遍历，查找并记录满足条件的最大展开全文