题意：
给你n个数vi，你有k次操作。每一次操作你可以从n个数里面挑一个数，然后使得这个数乘于一个正整数。操作完之后，这n个数里面不同数的数量就是权值。你要使得这个值尽可能小。
题解：
如果a%b==0 && a!=b
b%c==0 && b!=c
那么如果我们进行操作的话，肯定是把c变成a，因为这样消耗的最小操作数最少
我们最后的答案只需要在两种情况中取最小值就可以了
1、我们把n个数都往n个数的公倍数上变
2、如果这n个数里面出现了上面所示的a、b、c的情况，那么我们就把b、c这些数都往a上变
过程：
因为题目求的是操作完之后不同数的数量，那么我们首先记录一下每一个数的出现次数
然后在提前处理一下每一个数的倍数是否在这n个数里面
然后按照每一个数出现的次数排序。为什么？给你一个序列
1 1 2 4
我们如果只有一个操作，那么肯定是把2变成4.这样的话答案就是2
这就意味着，我们要使得1变成4的话，那么只有操作数大于等于3的时候才对最后的结果造成影响
之后就模拟就可以了
AC代码：
/* 有两种操作，要么是把一种数全部变成他的倍数（尽量大且存在的倍数），要么是将尽量多种类的数变成所有数的公倍数。 那么我们只需要维护出每种数是否存在其倍数，就只能这种数能否进行第一种操作。 只要对每个数因数分解，然后给因数打上标记，就可以知道每个数是否存在其倍数了。复杂度n*sqrt(t),t代表数据范围。 */ #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; const int INF=0x3f3f3f3f; const int mod = 1000000007; int v[maxn],num[maxn],vis[maxn],que1[maxn],que2[maxn]; int main() { freopen("equal.in","r",stdin); freopen("equal.out","w",stdout); int n; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&v[i]); num[v[i]]++; } for(int i=1;i<=n;++i) { int tmp=v[i]; if(tmp!=1) vis[1]=1; int ends=sqrt(tmp); for(int j=2;j<=ends;++j) { if(tmp%j==0) { vis[j]=1; vis[tmp/j]=1; } } } int pos1=0,pos2=0; for(int i=1;i<=1000000;++i) { if(num[i]==0) continue; int tmp=i; if(vis[tmp]) { que1[pos1++]=num[tmp]; } que2[pos2++]=num[tmp]; } sort(que1,que1+pos1); sort(que2,que2+pos2); //printf("%d****%d %d ",pos1,que1[0],que1[1]); int ans1=0,ans2=0,tmp1=0,tmp2=0; printf("%d ",pos2); for(int i=1;i<=n;++i) { tmp1+=1; while(tmp1>=que1[ans1] && ans1<pos1) { tmp1-=que1[ans1]; ans1++; } tmp2+=1; while(tmp2>=que2[ans2] && ans2<pos2) { tmp2-=que2[ans2]; ans2++; } if(i!=n) printf("%d ",pos2-max(ans1,ans2-1)); else printf("%d ",pos2-max(ans1,ans2-1)); } return 0; }