CF Div. 2 C

Codeforces Round 948 (Div. 2) C. Nikita and LCM

标签

暴力枚举

数据结构

[[数学]]

题目大意

有长度为n的数组a，求a中最长子序列的长度，子序列要满足 \(lcm(subArray(a)) \notin a\)

\(1 \le n \le 2000\) , \(1 \le a_i \le 10^9\) ,对于t个测试案例，\(sum(n) \le 2000\)

思路

1.分解问题

首先解决一个问题，假定有了数组a和一个数字k，要求\(lcm(subArray(a)) = k\) ，要如何实现

• 所有 \(a_i\) 判断是否是 \(k\) 的约数，然后将符合的所有 \(a_i\) 的lcm求出，如果是 \(k\) 说明成立

其次可以得到，假如枚举 \(k\) 值，再记录可行的 \(k\) 对应的 \(subArray(a)\) 的长度即可求解

2.优化方案

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

所有 \(lcm(subArray(a))\) 一定为 \(LCM\) 的约数，记作 \(k\) ，如果对于 \(k\) 满足条件，并且 \(k \notin a\) ，可以确定此时可行，记录结果。

3.代码

#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;
}