csp信奥赛C++之反素数-171主机测评

csp信奥赛C++之反素数

原题说明：洛谷P1463 反素数

题目描述

对于任何正整数

$x$ ，其约数的个数记作

(

)

g(x)

$g (x)$ 。例如

(

)

g(1)=1

$g (1) = 1$ ，

(

)

g(6)=4

$g (6) = 4$ 。

如果某个正整数

$x$ 满足：

∀

\\forall 0 \\lt i \\lt x

$\forall0 < i < x$ ，都有

(

)

(

)

g(x) \\gt g(i)

$g (x) > g (i)$ ，则称

$x$ 为反素数。例如，

1,2,4,6,12,24

$1, 2, 4, 6, 12, 24$ 等都是反素数。

现在给定一个正整数

$N$ ，你能求出不超过

$N$ 的最大的反素数么？

输入格式

仅一行一个正整数

$N$ 。

输出格式

仅一行一个正整数，代表不超过

$N$ 的最大的反素数。

输入输出样例 1

输入 1

1000

输出 1

840

说明/提示

对于所有数据，有

≤

1 \\leq N \\leq 2 \\times 10^9

$1 \leq N \leq 2 \times 1 0^{9}$ 。

暴力思路

问题理解反素数定义为：对于一个正整数 (x)，如果所有比 (x) 小的正整数 (i) 的约数个数都小于 (x) 的约数个数，那么 (x) 就是反素数。题目要求：在

∼

1 \\sim N

$1 \sim N$ 范围内，找出最大的反素数。

暴力思路

从 1到 N 逐个枚举每个数 x。
对于每个 (x)，计算它的约数个数 g(x)。
维护一个变量 mx 记录目前为止遇到的最大 g(x)，以及对应的数 ans。
如果当前 g(x) > mx，说明 (x) 比之前所有数都有更多的约数，因此它是反素数，更新 mx 和 ans。
遍历结束后，ans 即为不超过 N 的最大反素数。

计算约数个数的技巧

一个数的约数成对出现（除非是完全平方数，其中一对相等）。因此只需枚举到 $\\sqrt{x} x 。$
对于每个能整除 x 的 i，我们同时得到两个约数：i 和 x/i，所以计数器加 2。
如果 $\\times i = x i×i=x（即 x 是完全平方数），那么刚才加 2 时把同一个约数加了两次，需要减 1 修正。$

复杂度最坏情况下需计算每个数的约数个数，时间复杂度约为

(

)

O(N \\sqrt{N})

$O (N N$

)，对于

≤

N \\le 2\\times 10^9

$N \leq 2 \times 1 0^{9}$ 必然超时。

暴力代码（50分）

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

int n;

int main() {
cin >> n; // 输入上限 N

int mx = 0; // 记录当前找到的最大约数个数
int ans = 1; // 记录当前找到的反素数（初始为1）

// 枚举 1 到 N 的所有正整数 x
for (int x = 1; x <= n; x++) {
int cnt = 0; // 用于统计 x 的约数个数
int root = sqrt(x); // x 的平方根，只需枚举到 root

// 枚举 1 到 sqrt(x) 的所有数 i
for (int i = 1; i <= root; i++) {
if (x % i == 0) { // 如果 i 是 x 的约数
cnt += 2; // 则 i 和 x/i 都是约数，所以加 2
if (i * i == x) // 如果 i 恰好等于 x/i（即 x 是完全平方数）
cnt—; // 则刚才加多了 1 个，需要减去
}
}

// 如果当前 x 的约数个数严格大于之前所有数的约数个数
if (cnt > mx) {
mx = cnt; // 更新最大约数个数
ans = x; // 更新答案为当前 x
}
}

cout << ans << endl; // 输出不超过 N 的最大的反素数
return 0;
}

优化思路分析

1. 反素数的定义与性质

定义：一个正整数
直观理解：反素数就是在所有不超过它的数中，拥有最多约数个数的那个数。因此，反素数一定是“高度合成数”，但还必须保证前面没有数能与之持平或超过。

2. 约数个数的计算公式

若

$x$ 的质因数分解为：

⋯

x = p_1^{a_1} p_2^{a_2} \\cdots p_k^{a_k}

$x = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ 则其约数个数为：

(

)

(

)

(

)

⋯

(

)

g(x) = (a_1+1)(a_2+1)\\cdots(a_k+1)

$g (x) = (a_{1} + 1) (a_{2} + 1) \dots (a_{k} + 1)$

3. 反素数必须满足的两个重要性质

性质一：质因子必须是连续的最小质数

假设 $p_j pj 却包含了更大的质数 p t p_t pt，那么我们可以用 p j p_j pj 替换 p t p_t pt（保持指数不变），得到一个新的数 x ′ < x x' < x x′<x，但 g ( x ′ ) = g ( x ) g(x') = g(x) g(x′)=g(x)。这与反素数的定义矛盾（因为存在更小的数有相同的约数个数）。$
因此，反素数的质因子一定是从 2 开始的连续质数： $2,3,5,7,\\dots 2,3,5,7,…。$

性质二：指数单调不增（非递增）

假设 $2^{a_1}3^{a_2}\\cdots p_k^{a_k} x=2a13a2⋯pkak 是反素数，若存在 a i < a i + 1 a_i < a_{i+1} ai<ai+1（即指数递增），那么交换这两个指数，得到 x ′ = 2 a 1 ⋯ p i a i + 1 p i + 1 a i ⋯ x' = 2^{a_1}\\cdots p_i^{a_{i+1}}p_{i+1}^{a_i}\\cdots x′=2a1⋯piai+1pi+1ai⋯。由于 p i < p i + 1 p_i < p_{i+1} pi<pi+1，交换后 x ′ < x x' < x x′<x，但约数个数不变（因为指数集合相同）。同样存在更小的数有相同约数个数，矛盾。$
因此，指数必须满足 $a_1 \\ge a_2 \\ge \\cdots \\ge a_k \\ge 1 a1≥a2≥⋯≥ak≥1。$

4. 基于性质的搜索算法

利用上述两条性质，所有可能的反素数候选都可以通过**深度优先搜索（DFS）**枚举指数组合得到，并且可以大幅剪枝。

搜索框架

质数表：由于 $\\le 2\\times10^9 N≤2×109，我们只需考虑前几个质数。 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 ≈ 6.13 × 10 9 2\\times3\\times5\\times7\\times11\\times13\\times17\\times19\\times23\\times29\\approx 6.13\\times10^9 2×3×5×7×11×13×17×19×23×29≈6.13×109，已经超过 N N N，所以前 10 个质数足够。$
DFS 状态：
- cur：当前构造的数值。
- cnt：当前约数个数（根据公式累乘）。
- last：上一个质数使用的指数，当前质数的指数不能超过它（满足性质二）。
- pos：当前考虑第几个质数（从 0 开始）。
搜索过程：
每到达一个状态，首先检查是否需要更新答案：
- 若 cnt > mx（历史最大约数个数），则更新答案和最大值。
- 若 cnt == mx 且 cur < ans（数值更小），也更新答案（因为反素数要求数值本身最小）。
然后尝试为下一个质数（p[pos]）分配指数
i

i

$i$ ，从 1 到 last 枚举（注意指数至少为 1）。
- 累乘：new_cur = cur * p[pos]^i，但实际采用迭代乘法，防止幂运算开销。
- 如果 new_cur > N，则停止枚举更大的指数（剪枝）。
- 递归调用 dfs(new_cur, cnt*(i+1), i, pos+1)。
初始调用：dfs(1, 1, 31, 0)。
- cur=1，cnt=1（
- last 初始设为一个很大的数（31），因为第一个质数 2 的指数理论上限可达 $\\lfloor \\log_2 N \\rfloor ⌊log2N⌋，而 2 31 > 2 × 10 9 2^{31}>2\\times10^9 231>2×109，所以 31 足够大，相当于“无限”。$
- pos=0 表示从质数 2 开始。

5. 算法的正确性

完备性：所有可能的指数组合（满足指数非递增）都会被搜索到，因为递归树遍历了所有合法的指数分配。由于质数连续且指数单调，每个反素数必然对应一条搜索路径。
剪枝的正确性：当当前乘积超过
最优性：在搜索过程中，我们时刻用全局变量 ans 和 mx 记录当前最优值。由于搜索顺序（指数从大到小枚举）保证了先遇到的可能是较小数值，但最终通过比较更新，可以确保得到的是不超过

6. 时间复杂度分析

状态总数非常有限。对于 $N=2\\times10^9 N=2×109，指数组合的数目大约在几千量级（实际测试中递归次数不超过 5000），因此算法可以在毫秒级内完成。$

AC代码

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

// 质数表：前10个质数，因为2*3*5*7*11*13*17*19*23 ≈ 2.2e8，再乘29 ≈ 6.3e9 > 2e9
const int p[] = {2,3,5,7,11,13,17,19,23,29};
int n; // 输入上限
ll ans = 1; // 当前答案，初始为1
int mx = 1; // 当前最大约数个数，g(1)=1

// 深搜：cur 当前乘积，cnt 当前约数个数，last 上一质数的指数，pos 当前质数下标
void dfs(ll cur, int cnt, int last, int pos) {
// 更新答案：约数个数更大或相等但数值更小
if (cnt > mx || (cnt == mx && cur < ans)) {
mx = cnt;
ans = cur;
}
// 没有更多质数可选
if (pos >= 10) return;
ll tmp = cur; // 用于累乘
// 枚举当前质数 p[pos] 的指数 i，从1到last，并保证乘积不超过n
for (int i = 1; i <= last; ++i) {
tmp *= p[pos];
if (tmp > n) break; // 超出范围，停止枚举更大的指数
dfs(tmp, cnt * (i + 1), i, pos + 1);
}
}

int main() {
cin >> n;
dfs(1, 1, 31, 0); // last初始设为一个很大的数（31足以覆盖2^31>2e9）
cout << ans << endl;
return 0;
}

功能分析

以 (N=10) 为例，我们详细分析 DFS 算法的执行过程。算法利用反素数的性质（质因子连续且指数非递增）枚举所有可能的数，并动态更新最优解（约数个数最多且数值最小）。

初始状态

质数表：p[] = {2,3,5,7,11,13,17,19,23,29}（只需前几个）
全局变量：ans = 1（当前答案），mx = 1（当前最大约数个数）
初始调用：dfs(1, 1, 31, 0) 参数说明：当前乘积 cur=1，约数个数 cnt=1，上一指数 last=31（足够大），当前质数下标 pos=0（对应质数2）

递归树展开

第一层：质数 2

在 dfs(1,1,31,0) 中：

更新答案：cnt=1 与 mx=1 相等且 cur=1 等于 ans，不更新。
枚举指数 i 从 1 开始，累乘 cur 并确保不超过 N=10：

i=1：cur = 1*2 = 2，调用 dfs(2, 1*(1+1)=2, last=1, pos=1)

i=2：cur = 2*2 = 4，调用 dfs(4, 1*(2+1)=3, last=2, pos=1)

i=3：cur = 4*2 = 8，调用 dfs(8, 1*(3+1)=4, last=3, pos=1)

i=4：cur = 8*2 = 16 > 10，停止。

第二层：处理各个分支

分支 A：dfs(2,2,1,1)（当前质数 3）

更新答案：cnt=2 > mx=1 → 更新 ans=2, mx=2
枚举质数 3 的指数 i 从 1 到 last=1：
- i=1：cur = 2*3 = 6，调用 dfs(6, 2*(1+1)=4, last=1, pos=2)

分支 A1：dfs(6,4,1,2)（当前质数 5）

更新答案：cnt=4 > mx=2 → 更新 ans=6, mx=4
枚举质数 5 的指数 i 从 1 到 last=1：
- i=1：cur = 6*5 = 30 > 10，停止。
返回

分支 B：dfs(4,3,2,1)（当前质数 3）

更新答案：cnt=3 < mx=4，不更新
枚举质数 3 的指数 i 从 1 到 last=2：
- i=1：cur = 4*3 = 12 > 10，停止（后续更大指数更不可能）
返回

分支 C：dfs(8,4,3,1)（当前质数 3）

更新答案：cnt=4 == mx=4，但 cur=8 > ans=6，不更新
枚举质数 3 的指数 i 从 1 到 last=3：
- i=1：cur = 8*3 = 24 > 10，停止
返回

最终结果

所有递归结束后，全局变量 ans=6，mx=4，输出 6。

正确性验证

不超过 10 的正整数中，约数个数最多为 4，对应的数有 6、8、10。其中 6 是最小的，且所有小于 6 的数的约数个数均小于 4，因此 6 是反素数。算法通过 DFS 遍历了所有可能的候选（满足质数连续且指数非递增），并正确选出了最优解。

算法要点

每次进入 DFS 即检查更新，保证任何新数都被考虑。
利用质数连续和指数非递增性质大幅剪枝，避免无效枚举。
当乘积超过 N 时立即停止，确保只搜索合法范围。

【文末福利：一等奖秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

在这里插入图片描述

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转在这里插入图片描述

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

在这里插入图片描述

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

在这里插入图片描述

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

在这里插入图片描述 GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}

在这里插入图片描述