5112: Equal Numbers
时间限制: 3 Sec 内存限制: 512 MB
提交: 41
解决: 6
题目描述
You are given a list of n integers a1,...,an. You can perform the following operation: choose some ai and multiply it by any positive integer.
Your task is to compute the minimum number of different integers that could be on the list after k operations for all 0≤k≤n.
输入
The first line of the input contains single integer n (1≤n≤3≤105). The second line of the input contains n integers ai (1≤ai≤106).
输出
Output a single line that contains n + 1 integers. The i-th integer should be the minimum possible number of different integers in the list after i-1 operations.
样例输入
6
3 4 1 2 1 2样例输出
4 4 3 3 2 2 1【题意】
表示看不懂俄式英语。（题目竟然用some ai, 然后后面用it来代指，我搞不懂出题人从哪个国家学的英语，中国人看不懂）
有n个数，有一种操作：你可以选择其中任意一个数ai ，然后你可以把他乘上一个正整数。
问：当可以执行k次操作时，你可以得到的最小的 “不同数的个数”
【分析】
如果一个数的倍数在序列中出现了，那把他变成这个倍数，最有机会减少不同数目。
否则，只能把它变成他们的最小公倍数，或者不变（相当于乘1）
把每个数及出现次数统计，按出现次数排序，优先变次数少的。
【代码】
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
typedef long long ll;
const int N=1e6+5,mod=1e9+7,INF=0x3f3f3f3f;
struct node{
int x,c;
friend bool operator<(node a,node b){
if(a.c==b.c)return a.x<b.x;
return a.c<b.c;
}
}st[N],sr[N];
int a[N];
ll c[N];
ll r[N],t[N];
int main()
{
int n;
cin>>n;
rep(i,1,n)scanf("%d",&a[i]),c[a[i]]++;
int cnt=0,top=0;
ll lcm=1;
rep(i,1,N-1)if(c[i])
{
int flag=0;
for(int j=i+i;j<N;j+=i)if(c[j]){
flag=j;
break;
}
if(flag)sr[++cnt]=node{i,c[i]};
st[++top]=node{i,c[i]};
if(lcm<N)lcm=lcm*i/__gcd(lcm,(ll)i);
}
sort(sr+1,sr+1+cnt);
sort(st+1,st+1+top);
rep(i,1,cnt)r[i]=r[i-1]+sr[i].c;
rep(i,1,top)t[i]=t[i-1]+st[i].c;
printf("%d",top);
int last=top;
for(int i=1;i<=n;i++)
{
int ans=last;
if(i<=r[cnt]){ //可以变为倍数
int x=upper_bound(r+1,r+cnt+1,i)-r-1;
ans=min(ans,top-x);
//cout<<" "<<x;
}
int x=upper_bound(t+1,t+1+top,i)-t-1;
//cout<<" "<<x<<endl;
ans=min(ans,top-x+(lcm!=st[top].x));
if(i==n)ans=1;
printf(" %d",ans);
last=ans;
}
cout<<endl;
}