难度： 蓝

算法： 数学，素数判断，质数，筛法，搜索，打表

稍微有一点数论基础的人应该都能看出来满足条件的“反素数”在有限值域内 并没有多少个。

于是根据人类智慧我们可以打一个表，把所有的反素数都扔到表里面。

在下文中，令 $n=2\times 10^9,m=4.5\times 10^4>\sqrt n$。

为了实现求出所有反素数的目的，一种比较直观暴力的策略就是算出 $n$ 以内的所有数的约数。

我们将 $n$ 以内的每个数开一个队列，存储其小于等于 $m$ 的质因子。我们发现，对于 $n$ 以内的每个数，至多只有一个大于 $m$ 的质因子，且如果有的话，该质因子次数一定为 $1$。我们先筛出 $m$ 以内的所有质数并且给每个质数所对应的队列弹入这个质数本身。然后从 $1$ 至 $n$ 进行遍历。每遍历到一个数，就根据这个数对应的队列里的质因数，算出这个数的约数个数（别忘了这个数还可能有一个大于 $m$ 的质因子），然后，如果当前遍历到的数 $i$ 有小于 $m$ 的质因子 $u$，那么 $i+u$ 也必定有质因子 $u$，于是给 $i+u$ 所对应的队列弹入 $u$。

但这样显然是不可取的，因为空间达到了 $O(n)$，无法接受。考虑如何减少空间。我们对于每个数对应的质因子队列开一个双端队列（也就是双端队列套队列）维护。双端队列中保持只有 $m$ 个数。一开始将 $1$ 到 $m$ 的数放入其中。每遍历一个数时就在双端队列的队尾插入一个空队列，遍历完一个数后就将刚刚遍历完的队 列（也就是队首的队列）弹出。

上面这段话可能过于抽象，所以请看下面的代码。

注意：此代码使用文件输出，时间 $O(nlogn)$ 但是跑不满，空间 $O(\sqrt n)$。在我的电脑上用时 $1595s$。这个代码仅仅是生成反素数用的，并不是最终提交的代码。

#include<bits/stdc++.h>
using namespace std;
int n=2e9,m=45000;
int ans,res,cnt,num;
int f[45050],pr[45050],pc;
deque<queue<int> > q;
queue<int> t;
int main(){
	freopen("antiprimes.txt","w",stdout);
	for(int i=2;i<=m;i++){//线性筛 
		if(!f[i]) pr[++pc]=i;
		for(int j=1;j<=pc;j++){
			if(i*pr[j]>m) break;
			f[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
	for(int i=1;i<=m;i++){
		if(i!=1&&f[i]==0) t.push(i);
		q.push_back(t);
		if(!t.empty()) t.pop();
	}
	for(int i=1;i<=n;i++){//遍历 
		q.push_back(t);
		res=1;
		int k=i;
		while(!q[0].empty()){//枚举每个质因子 
			cnt=1;
			int u=q[0].front();
			q[0].pop();
			q[u].push(u);
			while(k%u==0){
				k/=u;
				cnt++;
			}
			res*=cnt;
		}
		if(k!=1) res*=2;
		if(res>ans){//检查是否为反素数 
			ans=res;
			printf("%d,",i);
			num++;
		}
		q.pop_front();
	}
	printf("\n%d",num);
}

根据上面的代码我们已经求出了 $n$ 以内的反素数。将这些反素数全部置入一个 vector。查询的时候使用 upper_bound 找就行了。

最终代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> k={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360};
int n;
int main(){
	scanf("%d",&n);
	int p=upper_bound(k.begin(),k.end(),n)-k.begin()-1;
	printf("%d",k[p]);
}