运维开发网

BZOJ1053: [HAOI2007]反素数ant

运维开发网 https://www.qedev.com 2020-03-27 10:28 出处:网络 作者:运维开发网整理
Description 对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足: g(x)>g(i)(0<i<x) ,则称x为反质数。例如,整数1,2,4,6等都是反质数。 现在给定一个数N,你能求出不超过N的最大的反质数么? Input 一个数N(1<=N<=2,000,000,000)。 Output 不超过N的最大的反质数。 Sample Input

Description

对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足: g(x)>g(i)(0<i<x) ,则称x为反质数。例如,整数1,2,4,6等都是反质数。

现在给定一个数N,你能求出不超过N的最大的反质数么?

Input

一个数N(1<=N<=2,000,000,000)。

Output

不超过N的最大的反质数。

Sample Input

1000

Sample Output

840

HINT

Source

转变一下思路,该题等价于不超过n的数中约数最多的数中的最小数(即若约数相等则取较小,因为题目要求是g(x)严格大于g(i)),利用反素数的一个性质:

一个反素数的所有质因子必然是从2开始的连续若干个质数

(应该还算比较好理解吧……自己想想就知道了)

所以本题就可以用递归来解决了。

#include<cstdio>
#define INT_MAX 2147483647
using namespace std;
int n,ans,ans1;
int p[16]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};//连续的素数
void read(int &x)
{
    char t=getchar();x=0;int f=1;
    while ((t<48)or(t>57)){if(t=='-')f=-1;t=getchar();}
    while ((t>=48)and(t<=57)){x=x*10+(int)t-48;t=getchar();}
    x*=f;
}
void dfs(int dep,int tmp,int num)
//dep表示深度,即p数组的一个指针,依次枚举
//tmp记录当前得到的数
//num表示tmp的约数个数
{
    if (dep>=16) return;
    if (num>ans1){ans1=num;ans=tmp;}//约数更多
    if ((num==ans1)and(tmp<ans)and(tmp<=n)) ans=tmp;//取较小值,防止相等
    for (int i=1;i<=31;++i)//log2(2000000000)≈31,枚举p[dep]的i次方
    {
        if (n/p[dep]<tmp) break;
        dfs(dep+1,tmp*=p[dep],num*(i+1));//递归
    }
}
int main()
{
    read(n);
    ans=INT_MAX;
    dfs(0,1,1);
    printf("%d",ans);
    return 0;
}
0

精彩评论

暂无评论...
验证码 换一张
取 消