洛谷 P1463 反素数【约数 | DFS】

题目链接

题目描述：

---

约数 ：

定义：

若整数 n 除以 d 的余数为0，即 d 能整除 n，则称 d 是 n 的约数，n 是 d 的倍数，记为 d | n 。

算术基本定理的推论：

在算术基本定理中，若正整数 N 被唯一分解为 $N=p_1^{c1}p_2^{c2}...p_m^{c_m}$N=p1c1​p2c2​...pmcm​​，其中 $c_i$ci​ 都是正整数，$p_i$pi​ 都是质数，且满足 $p_1<p_2<...<p_m$p1​<p2​<...<pm​，则 N 的正约数集合可写作：
$\{p_1^{b1}p_2^{b2}...p_m^{b_m}\}, 其中(0≤b_i≤c_i)${p1b1​p2b2​...pmbm​​},其中(0≤bi​≤ci​)
N 的正约数个数为：
$(c_1+1)*(c_2+1)*...*(c_m+1) = \prod_{i=1}^{m}(c_i+1)$(c1​+1)∗(c2​+1)∗...∗(cm​+1)=i=1∏m​(ci​+1)
N 的所有正约数的和为：
$(1+p_1+p_1^2+...+p_1^{c_1})*...*(1+p_m+p_m^2+...+p_m^{c_m})=\prod_{i=1}^{m}(\sum_{j=0}^{c_i}(p_i)^j)$(1+p1​+p12​+...+p1c1​​)∗...∗(1+pm​+pm2​+...+pmcm​​)=i=1∏m​(j=0∑ci​​(pi​)j)

求 N 的正约数集合——试除法

若 $d≥N^{\frac{1}{2}}$d≥N21​ 是 N 的约数，则 $N/d≤N^{\frac{1}{2}}$N/d≤N21​ 也是 N 的约数。换言之，约数总是成对出现的（除了完全平方数，$N^{\frac{1}{2}}$N21​ 会单独出现）。
因此，只需扫描 d = 1 ~ $N^{\frac{1}{2}}$N21​，尝试 d 能否整除 N，若能整除，则 N / d 也是 N 的约数。时间复杂度为 $O(N^{\frac{1}{2}})$O(N21​)。

int factor[1600], m = 0;
for (int i = 1; i * i <= n; i++) {
	if (n % i == 0) {
		factor[++m] = i;
		if (i != n / i) factor[++m] = n / i;
	}
}
for (int i = 1; i <= m; i++) 
	cout << factor[i] << '\n';

试除法的推论：

一个整数 N 的约数的个数上限上界为 2 * $N^{\frac{1}{2}}$N21​。

求 1 ~ N 每个数的正约数集合——倍数法：

若用“试除法”分别求出 1 ~ N 每个数的正约数集合，时间复杂度过高，为$O(NN^{\frac{1}{2}})$O(NN21​)。可以反过来考虑，对于每个数 d，1 ~ N中以 d 为约数的数就是 d 的倍数 $d,2d,3d,...,\lfloor n/d \rfloor*d$d,2d,3d,...,⌊n/d⌋∗d。以下程序用“倍数”法求出 1 ~ N 每个数的正约数集合：

vector<int> factor[500010];
for (int i = 1; i <= n; i++) {
	for (j = 1; j <= n / i; j++) {
		factor[i * j].pushback(i);
	}
}
for (int i = 1; i <= n; i++) {
	for (int j = 0; j < (int) factor[i].size(); j++)
		cout << fac[i][j] << " ";
	cout << '\n';
}

上述算法的时间复杂度为$O(N+N/2+N/3+...+N/N)=O(Nlog_2N)$O(N+N/2+N/3+...+N/N)=O(Nlog2​N)。

倍数法的推论：

1 ~ N 每个数的约数个数的总和大约为$Nlog_2N$Nlog2​N

---

题解：

引理 1：

1 ~ N 中最大的反质数，就是 1 ~ N 中约数个数最多的数中最小的一个。

证明：

设 m 是 1 ~ N 中约数个数最多的数中最小的一个。根据 m 的定义，m 显然满足：

1. $\forall x<m,g(x)<g(m)$∀x<m,g(x)<g(m)
2. $\forall x≥m,g(x)≤g(m)$∀x≥m,g(x)≤g(m)

根据反质数的定义，第一条性质说明 m 是反质数，第二条性质说明大于 m 的数都不是反质数，故 m 为所求。

引理 2：

1 ~ N 中任何数的不同因子都不会超过10个，且所有质因子的指数总和不超过30.

证明：

1. 因为最小的11个质数的乘积 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 > 2 * $10^9$109，所以 N ≤ 2 * $10^9$109不可能有多于10个不同的质因子。
2. 因为即使是只包含最小的质数，仍然有 $2^{31}>2*10^{10}$231>2∗1010，所以 N ≤ 2 * $10^9$109 的质因子指数总和不可能超过30。

引理 3：

$\forall x∈[1, N]$∀x∈[1,N]，x 为反质数的必要条件是：x 分解质因数后可写做 $2^{c_1}*3^{c_2}*5^{c_3}*7^{c_4}*11^{c_5}*13^{c_6}*17^{c_7}*19^{c_8}*23^{c_9}*29^{c_{10}}$2c1​∗3c2​∗5c3​∗7c4​∗11c5​∗13c6​∗17c7​∗19c8​∗23c9​∗29c10​，并且 $c_1≥c_2≥...≥c_{10}≥0$c1​≥c2​≥...≥c10​≥0。
通俗的讲，x 的质因数是连续的若干最小的质数，并且指数单调递减。

证明：

1. 反证法。由引理2，若 x 的质因数分解式中存在一项 $p^k(p>29)$pk(p>29)，则必定有一个不超过 29 的质因子 $p^{'}$p′ 不能整除 x。根据算术基本定理的推论，$x/p^k*p^{'k}$x/pk∗p′k 的约数个数与 x 的约数个数相等，但前者更小，这与反质数的定义矛盾。故 x 只包含 29 以内的质因子。
2. 同理，若 x 的质因子不是连续若干个最小的，或者指数不单调递减，我们也可以通过上述交换质因子的方法，得到一个比 x 更小，但约数个数相等的整数。因此假设不成立，原命题成立。

综上所述：

我们可以进行 DFS，尝试依次确定前 10 个质数的指数，并满足指数单调不递增、总乘积不超过 N，同时记录约数的个数。

---

AC代码：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(2);
//cout << setw(2);
const int N = 2e5 + 6, M = 1e9 + 7;

long long vis[50], prime[50], cnt;
long long ans = 2e9 + 1, mx = 0;
long long n;
void dfs(int x, long long now, int c, ll t) {
    if (x == 10) return;
    for (int i = 1; i <= c; i++) {
        ll res = now * pow(prime[x], i), sum = t * (i + 1);
        if (res <= n) {
            if (sum > mx) {
                mx = sum;
                ans = res;
            } else if (sum == mx) {
                ans = min(ans, res);
            }
            dfs(x + 1, res, i, sum);
        } else {
            return;
        }
    }
}

int main() {
    //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 2; i <= 29; i++) {
        if (vis[i] == 0) prime[cnt++] = i;
        for (int j = 0; j < cnt && prime[j] * i <= 29; j++) {
            vis[prime[j] * i] = 1;
            if ((i % prime[j]) == 0) break;
        }
    }
    dfs(0, 1, 30, 1);
    cout << ans << '\n';
    return 0;
}