LOJ 10203「一本通 6.3 例 1」反素数 Antiprime

题目链接

##题解 把\(n\)质因数分解一下，即\(n=\prod p-i^{k-i}\)
关于反素数的两个结论:
1. 如果两个数约数个数相同，那么更大的数不可能是反素数。
2. 我们枚举每个\(k-i\)，\(k-i\)一定是单调不增的。因为如果某个不满足条件的数是反素数，那么将\(k\)调整为单调不增的形式，得到一个比它小的数且约数个数相同，与题设矛盾。所以\(k-i\)一定是单调不增的。

有了以上结论，直接 dfs 枚举每个\(k-i\)。
因为最多只需要枚举到第\(\log_{2}^{2e9}\)个素数，且\(k\)不大，所以时间复杂度是正确的。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e9 + 5, M = 60;
int n;
int P[M], vis[M], cnt;
ll tot, ans;

void init(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) P[++cnt] = i;
		for (int j = 1; j <= cnt && P[j] * i <= n; j++) {
			vis[P[j] * i] = 1;
			if (i % P[j] == 0) break;
		}
	}
}
void dfs(int x, int lst, ll num, ll v) {
    if (num > tot || (num == tot && v < ans)) ans = v, tot = num;
    int cnt = 0;
    while (v * P[x] <= n && cnt < lst) {
    	v *= P[x];
    	cnt++;
    	dfs(x + 1, cnt, num * (cnt + 1), v);
    }
}

int main() {
    init(M - 5);
    scanf("%d", &n);
    dfs(1, 45, 1, 1);
    printf("%lld\n", ans);
    return 0;
}