问题描述:

 对于任何正整数$x$,其约数的个数记作$g(x)$。如果某个正整数$x$满足:$g(x)>g(i)$ 其中$0<i<x$,则称x为反质数。现在给定一个数$N$你需要找出不大于$N$的最大反素数。

输入:

一个数$N$($1<=N<=2000000000$)。

输出:

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

思路:

其实我们要求的就是$1-N$内约数个数最多的数(如果个数一样就是小的那个),然后我们可以利用一些神奇的性质用搜索解出答案。

首先反素数的质因子是不会超过10个的,并且质因子的指数是单调递减的。利用这两个性质缩小搜索范围,然后直接dfs枚举它的质因子就好了。

代码:

#include 
#define LL long long
using namespace std;

const int prime[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

LL n, maxsum, ans;

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum*=x;
        y>>=1; x*=x;
    }
    return sum;
}

void dfs(int id, int cnt, int sum, LL num)
{
    if(id==11)
    {
        if(sum>maxsum) ans=num, maxsum=sum;
        if(sum==maxsum) if(numn) break;
        dfs(id+1, i, sum*(i+1), num*ksm(prime[id], i));
    }
}

int main()
{
    scanf("%lld", &n);
    dfs(0, 30, 1, 1);
    printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注