牛牛有一个正整数数组A和一个正整数X，设A的长度为N，数组中的元素依次为A[0]~A[N – 1]。牛牛要挑选出符合以下条件的所有整数对(l, r)： 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

区块链毕设网qklbishe.com为您提供问题的解答

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

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

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

#include <functional>

#include <queue>

#include <unordered_set>

#include <vector>

class Solution {

public:

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* 求满足条件的第K大长度

* @param A int整型vector 牛牛的数组A

* @param X int整型至少要存在X个不同的质数

* @param K int整型牛牛希望找到第K大的长度

* @return int整型

vector<int> vp;

int GetKthLength(vector<int>& A, int X, int K) {

int mx = 0;

for (int i : A)

mx = max(mx, i);

func(sqrt(mx) + 1);

int len = A.size();

vector<unordered_set<int>> mask(len, unordered_set<int>());

for (int& i : vp) {

for (int j = 0; j < len; ++j) {

if (A[j] % i == 0 && A[j] != 0) {

mask[j].insert(i);

}

unordered_set<int> flg;

vector<map<int, int>> vmii(len, map<int, int>());

for (int i = len – 1; i >= 0; —i) {

auto p = mask[i].begin();

auto bd = mask[i].end();

while (p != bd) {

int tn = *p;

if (flg.count(tn)) {

++p;

continue;

}

int tl = 0;

for (int j = i; j >= 0; —j) {

if (mask[j].count(tn))

++tl;

else {

tl = 0;

continue;

}

++vmii[j][tl];

}

flg.insert(tn);

++p;

}

map<int, int, greater<>> mans;

int total = 0;

for (int i = 0; i < len; ++i) {

auto p = vmii[i].rbegin();

auto bd = vmii[i].rend();

int tot = 0;

while (p != bd) {

tot += p->second;

if (tot < X)

{

++p;

continue;

}

int tn = Cf(tot, X);

mans[p->first] += tn;

total = min(K, total + tn);

++p;

}

int tl = vmii[i].begin()->first – 1;

//cout << tot << endl;

int tnn = Cf(tot, X);

while (tl > 0 && total < K) {

mans[tl] += tnn;

total = min(K, total + tnn);

—tl;

}

int tK = K;

auto p = mans.begin();

auto bd = mans.end();

while (p != bd && tK > 0) {

tK -= p->second;

if (tK <= 0)

return p->first;

++p;

}

return –1;

// write code here

}

int Cf(int n, int m) {

if (n == m || m == 0) return 1;

vector<int> dp(m + 1);

for (int i = 0; i <= n; i++)

for (int j = min(i, m); j >= 0; j–)

if (i == j || j == 0) dp[j] = 1;

else dp[j] = dp[j] + dp[j – 1];

return dp[m];

}

void func(int n) {

vector<int> vn(n + 1, 1);

vn[0] = 0;

vn[1] = 0;

for (int i = 2; i <= n; ++i) {

if (vn[i] == 1)

vp.push_back(i);

int bd = vp.size();

for (int j = 0; j < bd && i * vp[j] <= n; ++j) {

vn[i * vp[j]] = 0;

if (i % vp[j] == 0)

break;

}

return;

}

};

07:23

以上就是关于问题牛牛有一个正整数数组A和一个正整数X，设A的长度为N，数组中的元素依次为A[0]~A[N – 1]。
牛牛要挑选出符合以下条件的所有整数对(l, r)：
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的答案

欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程

区块链NFT链游项目方科学家脚本开发培训