avatar

P1463 反素数

提供一个随便口胡的证明过程。

题目大意

设 $d(n)$ 表示 $n$ 的约数个数,求最大的 $x$ 满足 $\forall i \in (0, x), d(i)<d(x)$。

问题的转化

问题可以转化为:

  1. 求 $[1, n]$ 因数个数最多的数。
  2. 若相同的值有多个,则取最小值。

证明

假设 $x$ 为唯一的因数个数最多的数,显然 $x$ 一定是一个反素数。再假设有一个更大的反素数 $y$ 满足 $y > x,d(y) < d(x)$,则与反素数的定义相矛盾,故因数个数最多的数为区间内最大的反素数

如果存在多个相同的最大值,那么显然除了第一个,都不是反素数。

解法

根据唯一分解定理,我们有:对于任意一个正整数 $x$,它可以写成 $\prod p_i^{a_i}$,其中 $p_i$ 为质数,$a_i \in [0, \infin]$。

根据乘法原理,有 $d(x)=\prod(a_i + 1)$。

所以我们可以考虑搜索 $a_i$,求出 $d(x)$。

但是我们知道素数有无穷多个,所以我们需要进一步的推导。

结论:$a_i$ 是单调不升的。

证明

设 $x = \prod p_i^{a_i}$ 是反素数,其中 $a_i$ 是无序的。

设 $a_i$ 降序排序后变成了 $b_i$,$y = \prod p_i^{b_i}$,显然 $y < x$ 而 $d(y)=d(x)$。

根据上方问题转化-2,我们可以知道,$x$ 不是反素数,与假设相悖。

也就是说,$a_i$ 是有序的。

所以我们只需要前面的少数素数就可以了。

参考 oeis A002110 我们发现第 10 个素数的前缀积已经超过了数据范围,因此我们可以只用 10 个素数。

代码

根据以上的推理我们可以写出代码。

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

const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
int f[20], n, AnsNum, AnsDiv;

//dfs: {Current Depth, Current Number, Current Divisors}

inline void dfs(int dep, int num, int div) {
if(div > AnsDiv || (div == AnsDiv && num < AnsNum)) AnsNum = num, AnsDiv = div;
if(dep > 10) return;
int nxp = 1;
for(register int i = 1; i <= f[dep - 1]; i++) {
nxp *= prime[dep];
f[dep] = i;
int NewNum = num * nxp, NewDiv = div * (i + 1);
if(NewNum > n) break;
dfs(dep + 1, NewNum, NewDiv);
}
}

signed main() {
scanf("%lld", &n);
f[0] = 30;
dfs(1, 1, 1);
printf("%lld", AnsNum);
return 0;
}
文章作者: SocialZxy
文章链接: http://socialzxy.github.io/2020/03/27/P1463-%E5%8F%8D%E7%B4%A0%E6%95%B0/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 SocialZxy's Blog

评论