首页 > 试题广场 >

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

[编程题]能被多个质数整除的第K长子段
  • 热度指数：286 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛有一个正整数数组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
示例1

输入

[2, 2],1,2

输出

1

说明

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

备注:


算法知识视频讲解
添加回答
牛客708503815号头像 牛客708503815号
#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;
    }
};
发表于 2024-09-16 17:07:23 回复(0)
提交观点

问题信息

基础数学
难度：
1条回答 1442浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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