[洛谷 1463][POI2002][HAOI2007]反素数

题目链接

https://www.luogu.org/problem/P1463

题解

设 \(\{p_i\}\) 为递增排列的质数序列，将数 \(x\) 进行质因数分解：

$$x=\prod_{i=1}^{+\infty} p_i^{k_i}$$

当 \(p_i\) 递增的时候，\(k_i\) 只有递减才可能成为反质数（假如存在 \(i>j\)，且 \(k_i<k_j\) 的情况，可以交换两个 \(k\)，就可以在因数个数不变的情况下让数字变小）。

因此可以按这个规律进行搜索。

#include <iostream>
#include <algorithm>
using namespace std;
const int p[]={0,2,3,5,7,11,13,17,19,23,29,31,37};
int t[15],n;
long long ans,maxd;
void dfs(long long num,int cur,int d)
{
 if(cur>=13)return;
 if(d>maxd)ans=num,maxd=d;
 else if(d==maxd)ans=min(ans,num);
 long long tmp=num;
 for(int i=0;i<=t[cur-1]&&tmp<=n;i++,tmp*=p[cur])
 {
  t[cur]=i;
  dfs(tmp,cur+1,d*(i+1));
 }
}
int main()
{
 cin>>n;
 t[0]=50;
 dfs(1,1,1);
 cout<<ans<<endl;
 return 0;
}