题解

#include<cstdio>
#include<algorithm>
#define inf 0x7fffffffffffffff
using namespace std;
int p[17]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,57};
int num,tot;
long long a[100010],ans,n,b[100010],maxx;
inline void read(long long &x)
{
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return;
}
void print(long long x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
inline void dfs(long long x,int dep,long long tmp,int now)
{
	if(dep>=17)
		return;
	if(now>num)
		num=now,
		ans=tmp;
	if(now==num&&ans>tmp)
		ans=tmp;
	for(int i=1;i<=100;i++)
	{
		if(tmp>x/p[dep])
			break;
		dfs(x,dep+1,tmp*=p[dep],now*(i+1));
	}
}
void work(long long x)
{
	int l=1,r=tot,mid=l+r>>1;
	while(l!=r)
	{
		if(b[mid]>x)
			l=mid+1;
		else
			r=mid;
		mid=l+r>>1;
	}
	while(b[mid-1]<x&&b[mid-1])
		mid--;
	while(b[mid]>x)
		mid++;
	print(b[mid]);
	return;
}
int main(){
	read(n);
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		maxx=max(maxx,a[i]);
	}
	while(maxx!=1)
	{
		ans=inf;
		num=0;
		dfs(maxx,0,1,1);
		b[++tot]=ans;
		maxx=ans-1;
	}
	for(int i=1;i<=n;i++)
		work(a[i]),
		printf("\n");
	return 0;
}//§