题目描述 Description
如果一个自然数n满足:所有小于它的自然数的约数个数都小于n的约数个数,则称n是一个Antiprime数。譬如:1、2、4、5、12、24都是Antiprime数。
输入输出格式 Input/output
输入格式:
输入文件中只有一个整数n(1≤n≤2 000 000 000)。
输出格式:
输出格式:
输出文件中也只包含一个整数,即不大于n的最大Antiprime数。
输入输出样例 Sample input/output
样例测试点#1
输入样例:
1000
输出样例:
840
思路:
这个问题可以转化为求n以内约数最多的数,对于一个n,如果它的质因子越小,那么它能分解的因子个数也就越多,而对于有相同因子数的两个数,较小的那个更具有更新的空间,所以当两个数有相同因子数时,我们取较小一个。
根据唯一分解定理,任何一个大于1的数都可以分解为许多质数的乘积,并且根据质因数的个数可以算出约数的个数,公式为:n=P+P+PP,这个n的约数个数为(x+1)(y+1)(z+1)(…+1),那么这题,我们可以从1,从小到大循环,每次分解这个数为质因数,最终找到约数最多的数(约数相同取较少的,因为假如取较大的那个,因为较小的那个在前面,并且约数个数和较大的那个一样,这样就会出现较大的数不满足Antiprime数定义,所以我们取较小的数,这样前面就不会有数来和它冲突),输出即可。
但这样会超时,我们不妨做一下优化,逆用唯一分解定理,从小到大枚举每个质因数的使用个数(由数据范围限定最多枚举到23),搜索答案。
记住一定要用long long。
代码如下:
#include<cstdio>
#include<cmath>
long long n,maxx,num[]={,,,,,,,,,,},ans;
void findd(long long now,long long tot,long long u,long long v)//当前累计值,当前累计因数个数,上个质因数使用次数,枚举位置
{
if(maxx<tot||(tot==maxx&&ans>now))
{
maxx=tot;
ans=now;
}
if(v>=) return;
for(long long i=;i<=u;i++)
{
now*=num[v];
if(now>n) return;
findd(now,tot*(+i),i,v+);
}
}
int main()
{
scanf("%I64d",&n);
findd(,,,);
printf("%I64d\n",ans);
return ;
}