【SCOI2003】巴蜀1088 Antiprime数

本文主要是介绍【SCOI2003】巴蜀1088 Antiprime数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
　　如果一个自然数n（n>=1），满足所有小于n的自然数（>=1）的约数个数都小于n的约数个数，则n是一个Antiprime数。譬如：1,
2, 4, 6, 12, 24。 　　任务：编一个程序：
　　　　1、从ANT.IN中读入自然数n。
　　　　2、计算不大于n的最大Antiprime数。
　　　　3、将结果输出到ANT.OUT中。 Input 　　输入只有一个整数，n（1 <= n <= 2 000 000 000）。 Output 　　输出只包含一个整数，即不大于n的最大Antiprime数。

首先问题可以转化成求n以内约数最多的数，约数相同则取小的。
一个数x=a1^p1* a2^p2* …* an^pn(a是质数)的约数个数为(p1+1)* (p2+1)* …* (pn+1)。
考虑到2* 3* 5* 7* 11* 13* 17* 19* 23* 27>2e9，可以将27之前的素数打表，之后搜索每个素数的次数即可。
显然可以得到这个剪枝：从2向后，每个素数的指数单调不增。从而也有一个推论，就是不能跳着取素数。这样运行速度就很快了。

#include<cstdio>
#include<cstring>
int p[]={0,2,3,5,7,11,13,17,19,23,0},m,best;
long long n,ans;
void dfs(long long x,int k,int mx,long long now)
{if (now>best||(now==best&&x<ans)){ans=x;best=now;}if (!p[k]) return;int cnt=1;for (x*=p[k];x<=n&&cnt<=mx;x*=p[k],cnt++)dfs(x,k+1,cnt,now*(cnt+1));
}
int main()
{scanf("%lld",&n);dfs(1,1,1e8,1);printf("%d\n",ans);
}

这篇关于【SCOI2003】巴蜀1088 Antiprime数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---