lulaalu

标签

cnblogs

codeforces

字数

574 字

阅读时间

3 分钟

题目大意

有长度为n的数组a，求a中最长子序列的长度，子序列要满足 $l c m (s u b A r r a y (a)) \notin a$

$1 \leq n \leq 2000$ , $1 \leq a_{i} \leq 10^{9}$ ,对于t个测试案例， $s u m (n) \leq 2000$

思路

1.分解问题

首先解决一个问题，假定有了数组a和一个数字k，要求 $l c m (s u b A r r a y (a)) = k$ ，要如何实现

所有 $a_{i}$ 判断是否是 $k$ 的约数，然后将符合的所有 $a_{i}$ 的lcm求出，如果是 $k$ 说明成立

其次可以得到，假如枚举 $k$ 值，再记录可行的 $k$ 对应的 $s u b A r r a y (a)$ 的长度即可求解

2.优化方案

由于第一个子问题为 $O (2 n)$ 复杂度，从1枚举到1e9，是不可能的，那么我们可以用整个 $a$ 的 $L C M$

所有 $l c m (s u b A r r a y (a))$ 一定为 $L C M$ 的约数，记作 $k$ ，如果对于 $k$ 满足条件，并且 $k \notin a$ ，可以确定此时可行，记录结果。

代码

C++


#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<unordered_map> 

using namespace std;
#define int unsigned long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(i,j,k) for(i=(j);i<(k);i++)
#define all(x) begin(x),end(x)

const int N = 2000 + 10;
int ii, jj, kk;

int gcd(int a, int b) { return  (b == 0 ? a : gcd(b, a % b)); }

int lcm(int a, int b) { return ((b / gcd(a, b)) * a); }

int _, n;

// 子问题1
int check(vector<int>& v, int k) {
    vector<int>vv;
    for (auto i : v) {
        if (k % i == 0)
            vv.emplace_back(i);
    }
    int LCM = 1;
    for (auto i : vv) {
        LCM = lcm(LCM, i);
        if (LCM > k)return 0;
    }
    if (LCM == k)
        return vv.size();
    return 0;
}
void solve() {
    cin >> n;
    vector<int>v(n);
    unordered_map<int, int>mp; // 存储输入元素 优化方案中用于判断k是否属于a
    int LCM = 1; // a的总LCM
    for (auto& i : v) {
        cin >> i;
        mp[i]++;
    }
    int mx = *max_element(all(v)); // 最大元素
    for (auto& i : v) {
        LCM = lcm(LCM, i);
        if (LCM > mx) {  // 如果LCM大于mx，直接return
            cout << n << endl;
            return;
        }
    }

    int cnt = 0;
    for (int i = 1; i * i <= mx; i++) {
        if (mx % i == 0) {
            if (mp.count(i) == 0)   // 如果i是LCM约数且不是a中元素，
                cnt = max(cnt, check(v, i));
            if (mp.count(LCM / i) == 0)
                cnt = max(cnt, check(v, LCM / i));
        }
    }
    cout << cnt << endl;
    return;
}
signed main() {
    IOS;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

题目大意 ​

思路 ​

1.分解问题 ​

2.优化方案 ​

代码 ​

贡献者 ​

文件历史 ​

题目大意

思路

1.分解问题

2.优化方案

代码

贡献者

文件历史