Strange Beauty

Created by LXC on Thu May 25 00:38:03 2023

https://codeforces.com/problemset/problem/1475/G

ranting: 1900

tag: dp, math, number theory, sortings

problem

给出n个数的数组，求删除最少的数，使得任意两个数能够形成倍数关系。

solution

数据范围在1到n，可以考虑值域作为状态的参数。

$f_{x}$为不超过x的数中，能形成任意两个数都成倍数的最大个数。

$f_{x} = cnt_x + \sum \limits_{x \bmod i = 0} f_{i}$，其中$cnt_x$为x出现的次数。

预处理出1到n每个数的所有因子，时间复杂度O(nlogn)

找出最大状态值，便得到了最小需要删除的个数，$n-\max \limits_{i=1}^n f_i$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 200005
#define MOD 998244353
using namespace std;

vector<int> g[N];

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), c(N);
    for (int& i : a)
        cin >> i, c[i]++;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    vector<int> f(N);
    int ans = f[1] = c[1];
    for (int i : a) {
        for (int j : g[i])
            f[i] = max(f[i], c[i] + f[j]), ans = max(ans, f[i]);
    }
    cout << n - ans << "\n";
}

int main() {
    for (int i = 1; i < N; i++) {
        for (int j = 2 * i; j < N; j += i) {
            g[j].push_back(i);
        }
    }
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}