AW198 反素数

mac2022-06-30  228

题目地址


主要思路:

素因子累乘并利用题目限制条件更新答案.
#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; }

 


最新回复(0)