题目地址
主要思路:
素因子累乘并利用题目限制条件更新答案.
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int primes[26]={0,2,3,5,7,11,13,17,19,23,29,31,37},primeCnt=12;//质数表
int maxNum=-1,maxValue=-1;//最多的约数数量 最大反素数
int n;
void dfs(ll nowValue,ll nowNum,int nowIndex){//当前总值 当前约数数量 当前位于哪个质数
if(nowNum>maxNum){//如果约数数量更多则直接更新
maxNum=nowNum;
maxValue=nowValue;
}else if(nowNum==maxNum&&nowValue<maxValue)maxValue=nowValue;//约数数量相同的情况下优先选择尽量小的数
for(int i=nowIndex;i<=primeCnt;i++){
ll key=1;//当前质数乘方(多次)后的值
int tmp=1;
while(1){
key*=primes[i];//当前质数乘方(多次)后的值
if(nowValue*key>n)break;//如果总值超过n了则结束循环
dfs(nowValue*key,nowNum*(tmp+1),i+1);//合法则继续递归
tmp++;
}
}
}
int main(){
scanf("%d",&n);
dfs(1,1,1);//当前值为1,约数数量为1,位于第1个素数.
printf("%d\n",maxValue);
return 0;
}