反素数

发表于 更新于 分类于 阅读次数：

反素数 一个数论+搜索题 我们可以知道，对于正整数$x$，可以质因数分解为： $b^{c_1}_1 \times b^{c_2}_2 \times … \times b^{c_k}_k$ 由乘法原理易知，a的约数个数 $g(x)=({c_1}+1) \times ({c_2}+1) \times … \times ({c_k}+1)$ 易知$c$的顺序并不影响$g(x)$的值 我们可以将${c_1},{c_2}…{c_k}$从大到小排序，求出此时的$x$，则$x$最小 我们枚举所有的$c$，当$g(x)>maxg$时直接更新$ans$与$maxg$，当$g(x)=maxg,sum<ans$时更新sum

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
#include <bits/stdc++.h>
using namespace std;

int n;
long long max_g, ans;
int p[] = { 2,3,5,7,11,13,17,19,23,29,31,37,41 };

long long po(long long x, long long y) {
    long long a = 1;
    for (int i = 1; i <= y; ++i) {
        a *= (long long)p[x];
    }
    return a;
}

void dfs(long long g, long long sum, int k, int t) {
    if (g<0  sum<0  sum>n) return;
    if (g>max_g) ans = sum, max_g = g;
    if (g == max_g && sum<ans) ans = sum;
    if (t == 0) return;
    for (int i = t; i >= 0; --i) {
        dfs(g*(i + 1), sum*po(k, i), k + 1, i);
    }
}

int main() {
    cin >> n;
    dfs(1, 1, 0, 31);
    cout << ans;
    return 0;
}