GCD of Subset

 法1： 

const int N=1e6;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,k; cin>>n>>k;vector<int>a(n+1),cnt(N+10);/*桶cnt不要用map实现！！！速度太慢*/vector<vector<int>>v(N+10);for(int i=1;i<=n;i++) cin>>a[i];/*预处理1~N每个数的因数,复杂度O(调和级数),n=1e6,计算次数在1e8出头,1e8跑一下100ms~200ms,push_back一下1000ms了*/for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i)v[j].push_back(i);/*v[j]的因子按升序加进来*//*统计数组a中含有因子x的数的个数*/for(int i=1;i<=n;i++)for(auto x : v[a[i]])cnt[x]++;for(int i=1;i<=n;i++){int ans;for(auto x: v[a[i]])if(cnt[x]>=k)ans=x;cout<<ans<<endl;}
}

预处理每个数的因子1000ms多了

法2：

const int N=1e6;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,k; cin>>n>>k;vector<int>a(n+1),cnt(N+10),mp(N+10),ans(N+10);for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}for(int i=1;i<=N;i++){for(int j=i;j<=N;j+=i)cnt[i]+=mp[j];if(cnt[i]<k) continue;for(int j=i;j<=N;j+=i)ans[j]=i;}for(int i=1;i<=n;i++)cout<<ans[a[i]]<<endl;
}

 二者都去统计了数组a中，含因子x的数的个数。对于数量大于等于k的因子x，更新a中所有以x为因子的数的答案

数据大时，桶最好手写（直接写数组），map耗时间。

1+1/2+1/3+...+1/n约1e8 (n取1e6)

#调和级数 #枚举 

25/2/16