反素数-约数

反素数

P1463 反素数

题意

定义如果 x 的约数个数严格大于 0-x 所有数的约数个数，即 \(\forall 0<i<x\) ，都有 \(g(x) \lt g(i)\)，则称 x 为反素数。给定 n ，求出不超过 n 的最大反素数。

思路

设 \(x = \prod p_i^{k_i}\)，则显然 \(d(x) = \prod (k_i + 1)\) 。如果 \(k_x < k_y\) 并且 \(x < y\)，那么显然这个数不可能是反素数，因为交换 \(k_x\) 和 \(k_y\) 会更好。并且前 \(12\) 个素数的积 \(>2×10^9\) ，所以最多用到 \(12\) 个素数,直接搜索的时间复杂度。。有点难算，反正挺快。

code

#include <bits/stdc++.h>
#define int long long 
using namespace std;
constexpr int maxn = 1e5+10;int n;
int ss[20]={0,2,3,5,7,11,13,17,19,23,29};
int ans=0,ma=0;void dfs(int dep,int tal,int lst,int gs)
{// 当前素数下标，乘积-值，上一个素数个数，约数个数if(tal*ss[dep]>n)// 如果放不了了{if(gs>ma){ma=gs;ans=tal;}else if(gs==ma){ans=min(ans,tal);}return;}int cheng=1;for(int i=1;i<=lst;++i){cheng*=ss[dep];if(tal*cheng>n){break;}dfs(dep+1,tal*cheng,i,gs*(i+1));}
}signed main()
{scanf("%lld",&n);dfs(1,1,32,1);// 2，初始为1，2^32printf("%lld",ans);return 0;
}