参考博客链接:#10203. 「一本通 6.3 例 1」反素数 Antiprime
原题来自:POI 2001
如果一个大于等于 1 的正整数 n,满足所有小于 n 且大于等于 1 的所有正整数的约数个数都小于 n 的约数个数,则 n 是一个反素数。
譬如:1,2,4,6,12,241, 2, 4, 6, 12, 241,2,4,6,12,24,它们都是反素数。
请你计算不大于 n 的最大反素数。
输入格式
一行一个正整数 n。
输出格式
只包含一个整数,即不大于 n 的最大反素数。
样例
Input
1000
Output
840
#include<bits/stdc++.h>
using namespace std;
int a[12]={0,2,3,5,7,11,13,17,19,23,29};
#define ll long long
ll n,s,c;
//s为最优解,c为约数总个数
void dfs(ll x,ll y,ll b,ll z)
{
//x为第几个质因子
//y为当前乘积
//b为为每个质因子取值范围
//z为已得到y的约数个数
if(x==11) return ;
ll k=1;
for(int i=1;i<=b;i++)//当前递归的质因子的个数不超过b
{
k*=a[x];//质因子次幂p^r
if(y*k>n)//当前求得值已经大于n,那么就没必要再继续递归下去,直接返回
return ;
if(z*(i+1)==c&&y*k<s) s=y*k;//如果约数个数相同,返回最小的
如果y的约数个数z大于之前求到的最大的约数个数c,那就更新c,并且更新s;
if(z*(i+1)>c) s=y*k,c=z*(i+1);
dfs(x+1,y*k,i,z*(i+1));//往下递归
}
}
int main()
{
scanf("%lld",&n);
dfs(1,1,31,31);
printf("%lld\n",s);
}
版权声明:本文为weixin_52513845原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。