链接:

https://www.acwing.com/problem/content/200/

题意:

对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。

如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。

例如，整数1，2，4，6等都是反素数。

现在给定一个数N，请求出不超过N的最大的反素数。

思路:

考虑前11个素数的乘积大于2e9, 可以对n用前10个质数进行质数分解.

考虑2^31 > 2e9. 然后限制一下范围, DFS跑一遍.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MAXV = 2e9;

int Pri[20] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

int Cnt[20];

LL cnt, res, n;

LL Pow(LL a, int b)

{

    LL tmp = 1;

    while (b > 0)

    {

        if (b&1)

            tmp *= a;

        a *= a;

        b >>= 1;

    }

    return tmp;

}

void Dfs(int step, LL val)

{

//    cout << step << ' ' << val << endl;

    if (step > 10)

    {

        LL tmp = 1;

        for (int i = 1;i <= 10;i++)

            tmp *= (Cnt[i]+1);

        if (tmp > cnt)

        {

            cnt = tmp;

            res = val;

        }

        else if (tmp == cnt && val < res)

        {

            cnt = tmp;

            res = val;

        }

        return;

    }

    for (int i = 0;i <= 30;i++)

    {

        if (val*Pow(Pri[step], i) > n)

            break;

        Cnt[step] = i;

        Dfs(step+1, val*Pow(Pri[step], i));

    }

}

int main()

{

    memset(Cnt, 0, sizeof(Cnt));

    scanf("%lld", &n);

    if (n == 1)

    {

        puts("1");

        return 0;

    }

    Dfs(1, 1);

    printf("%lld\n", res);

    return 0;

}

巴特西

Acwing-198-反素数(约数, 数学)

链接:

题意:

思路:

代码:

最新文章

热门文章