没啥好说的,直接爆搜完事
事后发现质数表只用几个就可以了…不需要欧拉筛
没办法,谁叫我这么弱呢
代码如下:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,ans,a[1000],qwq;
ll l,r,p[1010],tot;
bool v[1001];
void prime()
{
for(int i=2;i<=1000;i++)
{
if(v[i]==0)p[++tot]=i;
for(int j=1;j<=tot&&p[j]*i<=1000;j++)
{
v[p[j]*i]=1;
if(i%p[j]==0)break;
}
}
}
void dfs(ll x,ll sum,ll y)
{
sum/=(a[y]+1);
x*=p[y];
a[y]++;
sum*=(a[y]+1);
if(x>n||(sum<=qwq&&x>=ans))
{
a[y]--;
return;
}
if(sum>=qwq)
{
qwq=sum;
ans=x;
}
if(a[y+1]<a[y])dfs(x,sum,y+1);
if(a[y]<a[y-1])dfs(x,sum,y);
a[y]--;
}
int main()
{
prime();
scanf("%lld",&n);
a[0]=1e9;
p[0]=1;
dfs(1,1,1);
printf("%lld",ans);
}
%%%打表
%%%