BZOJ1053 - [HAOI2007]反素数ant

2017/02/21

开学考果不其然炸飞了 _(:з」∠)_。要好好好好好好学习?

题目

对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足:对于任意 0 < i < x,都有 g(x) > g(i),则称x为反质数。例如,整数1,2,4,6等都是反质数。现在给定一个数N,你能求出不超过N的最大的反质数么。

补充背景:
反素数也叫 Highly composite numbers (OEIS)

解法

看到题我是萌比的,因为完全没有思路啊 Σ( ° △ °|||),我说我不会写,但是你们又不高兴……

首先说到约数个数公式,这个我博客里面有说过一次:对于数的质因数幂次表示 ,其因数个数为

通过这个公式不难看出来,一个合法的解应该有这样的特点:将它的质因数幂次表示按照质因子底数从小到大排序,那么次数应该是单减的。(这样保证了它是最小的一个)

所以说就可以写一个搜索了,从小到大枚举每个质因数出现的次数(单减),顺带更新答案。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned long long ULL;
const ULL Pri[100] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
ULL N;
ULL ans, num;

void dfs(ULL now, ULL prod, ULL cs, ULL lastcs, ULL res) {
    if(ans == res * (cs + 1) && prod < num)
        num = prod;

    if(res * (cs + 1) > ans) {
        ans = res * (cs + 1);
        num = prod;
    }

    if(cs+1 <= lastcs && prod * Pri[now] <= N) {
        dfs(now, prod * Pri[now], cs + 1, lastcs, res);
    }

    for(int i=now+1; i<=10; i++) {
        if(prod * Pri[i] <= N)
            dfs(i, prod * Pri[i], 1, cs, res * (cs + 1));
    }
}

int main() {
    scanf("%llu", &N);
    dfs(1, 1, 0, 100, 1);
    printf("%llu", num);
    printf("\n");
}