反素数

发表于 | 分类于

反素数

模板

反素数定义：对于正整数\(n\)，任何比\(n\)小的数正约数个数都小于\(n\)的正约数个数，则称\(n\)是反素数。

反素数性质：

性质1：若正整数\(n\)是反素数，则\(n\)的质因数是若干个最小的质数的乘积，且它们的指数单调不增。

性质2：不大于\(n\)的最大反素数是\(1,2,\cdots n\)中约数最多的数中最小的。

基于反素数的以上性质，我们可以采用dfs搜索查找反素数，分别确定每个质因数的指数，更新最大的约数个数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long long p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};//列举前几个素数
long long n,ans,ans_num;
void dfs(int d,long long tmp,long long num,int mi)
{
    if(d >= 16 || tmp > n)
    return ;//超出边界则返回
    if(num > ans_num || (num == ans_num && tmp < ans))
    {
        ans_num = num;
        ans = tmp;
    }//更新约数个数
    for(int i = 1;i <= mi;i++)//枚举第d个质数的指数
    {
        if(tmp * p[d] > n)
        break;
        tmp = tmp * p[d];
        dfs(d + 1,tmp,num * (i + 1),i);
    }
}

例题

CF27E A Number With The Given Amount Of Divisors

题目链接：https://codeforces.com/problemset/problem/27/E

题意

给定一个正整数\(n\)，求约数个数恰好是\(n\)的最小正整数。

数据范围

\(1\leq n \leq 1000\)，所求正整数不大于\(10^{18}\)。

题解

易知这样的\(n\)满足反素数的性质，在dfs的时候将约数等于\(n\)作为更新的条件即可。

代码 

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
#include<iostream>
#define maxn 1e18
using namespace std;
long long p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
long long ans,n;
void dfs(int d,long long tmp,long long num,int mi)
{
    if(d > 16 || tmp > maxn)
    return ;
    if(n == num && tmp < ans)
    ans = tmp;
    for(int i = 1;i <= mi;i++)
    {
        if(p[d] * tmp > maxn)
        break;
        tmp = tmp * p[d];
        dfs(d + 1,tmp,num * (i + 1),i);
    }
}
int main()
{
    cin >> n;
    ans = maxn;
    dfs(0,1,1,63);
    cout << ans;
    system("pause");
    return 0;
}