Opening a blog for the first time!

Revision en3, by Please_do_not_play_me, 2021-01-26 17:28:54

Write down the solution of yesterday's Div3.G question.

G.Strange Beauty

The topic is to require a maximum set so that the numbers directly multiply with each other.Sorting does not affect the results.Let's let ${f_i}$ represent the number of sets with the largest number in i.

Then an obvious state transition equation:${f_i=f_j+num_i}$.In which ${num_i}$ represents the number of i.

The next step is to consider the problem of transferring time.Obviously I can only be transferred by the factor of i.Notice that the data size is only 2e5.We might as well preprocess all the factors with an Ehrlich sieve.Then carry out dp.

The time complexity is ${O(nlognlogn)}$.

code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
vector<int>v[N];
void init()
{
for(int i=1;i<=2e5;i++)
{
for(int j=i;j<=2e5;j+=i)
{
v[j].push_back(i);
}
}
}

int main()
{
int T;scanf("%d",&T);
init();
while(T--)
{
unordered_map<int,int>p,f;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);p[a[i]]++;
}int ans=0;sort(a+1,a+1+n);
int cnt=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=cnt;i++)
{
f[a[i]]=p[a[i]];
for(int j:v[a[i]])
{
if(a[i]!=j) f[a[i]]=max(f[a[i]],f[j]+p[a[i]]);
}ans=max(f[a[i]],ans);
}
printf("%d\n",n-ans);
}
return 0;
}



#### History

Revisions

Rev. Lang. By When Δ Comment