#10203. 「一本通 6.3 例 1」反素数 Antiprime

参考博客链接:#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版权协议,转载请附上原文出处链接和本声明。