1625： 【例 1】反素数 Antiprime
【题目描述】
原题来自：POI 2001
如果一个大于等于 1
的正整数 n，满足所有小于 n 且大于等于 1 的所有正整数的约数个数都小于 n 的约数个数，则 n 是一个反素数。譬如：1,2,4,6,12,24
，它们都是反素数。
请你计算不大于 n
的最大反素数。
【输入】
一行一个正整数 n
。
【输出】
只包含一个整数，即不大于 n
的最大反素数。
【输入样例】
1000
【输出样例】
840
【提示】
数据范围与提示：
对于 10% 的数据，1≤n≤103
；
对于 40% 的数据，1≤n≤106
；
对于 100% 的数据，1≤n≤2×109
。
这道题是一本通的例题，虽然代码很短但是注释过于简单不变理解，洛谷大佬的题解太长又不想看。。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[]={,,,,,,,,,,};
ll n,s,s1;
void dfs(ll x,ll y,ll b,ll z)
{
if(x==) return ;
ll i,k=;
for(i=;i<=b;i++)
{
k*=a[x];
if(y*k>n) return ;
if(z*(i+)==s1&&y*k<s) s=y*k;
if(z*(i+)>s1)
{
s=y*k;
s1=z*(i+);
}
dfs(x+,y*k,i,z*(i+));
}
}
int main()
{
scanf("%lld",&n);
dfs(,,,);
printf("%lld",s);
return ;
}
在上面的代码中：x表示目前检索的是第几个质因子；
y表示目前已经得到的Antiprime；
b表示上一个书的指数（所以i 才会从一开始循环到b就结束）
z表示当前所取到的约数个数。
s1表示的是目前可以取到的最大约数个数；s表示当前最小的Antiprime（即答案）