反素数(求约数个数)
发布时间
阅读量：
阅读量
对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。
如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。
例如，整数1，2，4，6等都是反素数。
现在给定一个数N，请求出不超过N的最大的反素数。
输入格式
一个正整数N。
输出格式
一个整数，表示不超过N的最大反素数。
数据范围
1≤N≤2∗109
输入样例：
1000
输出样例：
840
思路：根据反素数的定义：求一个数的约数个数比起小于它的数的约数个数都多的数，可以总结出判定1~n中最大反素数 的两条性质：
1、约数个数最多
2、满足上一条性质的前提下，最小的数
因为*一个数可以分解为其素因子之积的形式，即：p1c1*p2c2*...pn^cn,
所以，其约数个数为：(c1+1)(c2+1)..*(cn+1)
约数之和为:(p10+p11+..p1c1)*(p20+p21+..p2c2)...(pn0+pn1+..pn^cn) ,(因为将该式展开每一项即为一个约数)
这里只用到了约数个数且用到的素数最大29就够了，因此只要dfs求1~n中出约数个数最多且最小的数 即可，在dfs时，因为要使约数个数尽可能达到最多，所以越小的素因子的幂次一定尽可能多（分解成小的一定比分解成大的个数多），所以当前质因子的幂次一定小于等于上一个素因子的幂次，也就是说枚举每个素因子的幂次c时，从小到大枚举每个素因子并且素因子的幂次一定是呈递减趋势的，最后每个素因子的幂次+1的乘积（(c1+1)(c2+1)..*(cn+1)）即为当前方案的约数个数，取所有方案最大的个数即为答案。
完整代码：
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int primes[]={2,3,5,7,11,13,17,19,23,29};
int sum,res,n;
void dfs(int u,int lastmi,int num,int cnt)//u：当前素数，lastmi：上一个素数的幂次，num：当前素数乘积表示的反素数，cnt：当前反素数num的约数个数
{
if(cnt>sum||sum==cnt&&num<res){
sum=cnt;
res=num;
}
for(int i=1;i<=lastmi;i++){
int p=primes[u];
if(num*p>n) break;
num*=p;
dfs(u+1,i,num,cnt*(i+1));
}
}
signed main()
{
cin>>n;
dfs(0,30,1,1);
cout<<res<<endl;
return 0;
}
全部评论 (0)
还没有任何评论哟~