原题链接
\(非常简单的一道预处理题\)
\(通过小学知识我们可以知道1-1e6内的数平均因数个数为13.6\)
\(所以我们通过枚举每个数的所有质因子 再通过对质因子dfs求出其所有的因子 最坏复杂度为O(n*sqrt(inf))\)
\(在通过一个后缀处理掉所有的因子数\)
\(通过后缀往前更新答案\)
\(code:\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int vis[1000010];
int ans[1000010];
int ok[100010];
void solve() {
int n;cin>>n;
function<void(map<int,int>,vector<int>,int,int)>dfs=[&](map<int,int>mp,vector<int>p,int dep,int now){
int pw=1;
if(dep==p.size()){
vis[now]++;
return;
}
for(int i=0;i<=mp[p[dep]];i++){
if(i)pw*=p[dep];
dfs(mp,p,dep+1,now*pw);
}
};
auto ck=[&](int x){
map<int,int>mp;
vector<int>p;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0)p.pb(i);
while(x%i==0){
mp[i]++;
x/=i;
}
}
if(x>1)mp[x]++;
if(mp.count(x)==1)p.push_back(x);
dfs(mp,p,0,1);
};
for(int i=1;i<=n;i++){
int x;cin>>x;
ck(x);
}
int mx=1;
for(int i=1;i<=1e6;i++){
if(vis[i]){
ans[vis[i]]=i;
}
}
for(int i=1e6;i>=1;i--){
ans[i]=max(ans[i],ans[i+1]);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}