bzoj1053 [HAOI2007]反素数ant

时间:2022-07-12 18:37:43

1053: [HAOI2007]反素数ant

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 3410  Solved: 1989
[Submit][Status][Discuss]

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
分析:这道题让我们求这样一个数:1.因数最多 2.如果满足1条件的有多个,则取最小的那一个.
       根据唯一分解定理可以得到:x = p1^k1 * p2^k2 *...*pn^kn,其中p1,p2,...,pn为质数,这样有多少个因数呢?根据乘法原理,质数p1可以不选,选1个,2个...k1个,p2到pn也是类似,那么因数个数=(k1 + 1)*(k2 + 1)*...*(kn + 1).
       显然,用小质数比用大质数更好,又因为2*3*5*7*11*13*17*19*23*29=6,469,693,230>2,000,000,000,所以我们只需要用到前9个质数就可以了!这样,我们搜索每个质数的次数,更新答案就可以了。如果在搜索中数的大小超过了n,就剪枝。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

long long n,ans = 2000000000;
int sushu[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 },a;

void dfs(long long num, int cishu, int cnt)
{
    if (cnt > 9)
        return;
    if (cishu > a)
    {
        ans = num;
        a = cishu;
    }
    if (cishu == a && num < ans)
        ans = num;
    for (int i = 1; i <= 31; i++)
    {
        if (num * sushu[cnt] > n)
            return;
        dfs(num * sushu[cnt], cishu *(i + 1), cnt + 1);
        num *= sushu[cnt];
    }
}

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

    return 0;
}