acwing198反素数（题解）-Toy模板网

这篇具有很好参考价值的文章主要介绍了acwing198反素数（题解）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

对于任何正整数 x，其约数的个数记作 g(x)，例如 g(1)=1、g(6)=4�(1)=1、�(6)=4。

如果某个正整数 x满足：对于任意的小于 x 的正整数 i，都有 g(x)>g(i)，则称 x为反素数。

例如，整数 1，2，4，61，2，4，6 等都是反素数。

现在给定一个数 N，请求出不超过 N 的最大的反素数。

输入格式

一个正整数 N。

输出格式

一个整数，表示不超过 N 的最大反素数。

数据范围

1≤N≤2∗109

输入样例：

输出样例：

思路：

最大反素数（我设为x）=拥有最多约数的一批数中的最小数。

如果x不是拥有最多约数，x1拥有最多约数：

假如x1<x,不符合反素数定义；x1>x，x不是最大的反素数。

任意正整数n=(x有k种质因子，pi是第i种质因子，ci是pi的次数)

x的质因子分解会是{2，3，5，7，11，13，17，23，29}的连续质因子的组合，并且c1>=c2>=c3>=c4.....并且c1+c2+c3+...c10<30.

如果x的质因子分解不是连续的，则较大的质因子可以被缺少的质因子替代，则存在x1<x，x1和x拥有相同的约数个数。

x的质因子如果有超过29的，2*3*5...*31>2*1e9;

c1>=c2>=c3>=c4.....如果不满足，比如c3>c1，那么将c3，c1调换，获得x1<x，x1和x拥有相同的约数个数。

2^31>2*1e9

所以我们得知：

x的质因子分解会是{2，3，5，7，11，13，17，23，29}的连续质因子的组合，并且c1>=c2>=c3>=c4.....

深搜dfs即可；

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
#define LL long long
const int N = 1e6 + 1000;
const long long mod = 1e9 + 7;
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
LL n, mxin=1e18,cnt,y;
int a[20] = { 0,2,3,5,7,11,13,17,19,23,29};
unordered_map<int, int> p;
void dfs(LL no, LL w, int last,LL yue)//w是x，last是一个选的次数,yue是总约数个数。
{
if (yue > cnt||yue==cnt&&w<mxin)
{
mxin = w;
cnt = yue;
}
if (no == 10) return;
LL x = a[no];
for (int i = 1; i <= last; i++)
{
if (w * x > n) break;
dfs(no + 1, w*x, i, yue*(i+1));
x *= a[no];
}
}
int main()
{
cin >> n;
dfs(1, 1, 31,1);
cout << mxin << endl;
return 0;
}文章来源地址https://www.toymoban.com/news/detail-729179.html