1 条题解
-
0Guest LV 0
-
0
#include<bits/stdc++.h>
using namespace std;
long long n,ans=0,maxn=0;//maxn=每个小于n的数总约数和
long long a[15]={0,2,3,5,7,11,13,17,19,23,29};
//约数个数求法:设m=2^a+3^b+……+p^?(p是最大的质数) 则约数个数为(a+1)*(b+1)*……*(p+?)
void solve(long long seat,long long value,long long limits,long long amount)
{
//seat=质因数位置 value=当前累计值 limits=每个质因数范围 amount=当前累计因数个数
if(maxn<amount||(maxn==amount&&ans>value))
{// 当每发现一个约数和比当前在计算的数的约数和还大的数时 || (两个数的总约数和相等&&但其中一个数大于另外一个数)
ans=value;//找出最大的Antiprime数
//这里注意是要选择一个相比更小的数 因为题目要求不大于n 所以每找出几个总约数和相等的数 就选最小的那个数
//以免这个数大于n
maxn=amount;//赋值maxn等于目前所能找到的最多的约数和的数的约数总和
}
if(seat==11) return ;//数据最大为2*10^9 所以质因子数最多10个
for(long long i=1;i<=limits;i++)
{
value*=a[seat];
if(value>n) return ;
solve(seat+1,value,i,amount*(i+1));
//solve(下一个质因数,当前累计值,一直递归到当前这个质因数最大使用范围,统计当前质因数使用个数)
}
}
int main()
{
cin>>n;
solve(1,1,31,1);//数据最大为2*10^9 2^31次 递归层数最大也就31
cout<<ans<<endl;
return 0;
}
//来自某届石光中学信竞苟蒻学长 愿看到此文的你 努力码题 为校争光
- 1