GCDofSubset

 法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