P1463 [POI2001][HAOI2007] 反素数

100%数据时，N<=2e9，即使使用线性的欧拉筛也会TLE

如此大的数据范围，O（1）的时间复杂度都跑不过，

说明要么打表，要么就需要通过计算直接得出答案，而非一个一个数地判断

通过分析，这道题的要求是找出小于等于N的数中

约数个数最多，并且最小的数，称为“反素数”

每一个数都可以表示成几个素数（可能相同）的乘积

比如6=2*3 12=2*2*3

即一个数n=a1^b1*a2^b2*……*an^bn

( a1<a2<……<an && b1>=b2>=……>=bn )

而这个数的约数个数为几个素数指数各加一的乘积

证明很简单

每个素数指数从0到最大作为其某个约数的约数

每个素数可以有指数加一种选择方式

因此这个数约数个数即为

（b1+1）*(b2+1)*……*(bn+1)

其中an不超过31，

因为题目要求约数最多且最小

即MAX（b1+1）*(b2+1)*……*(bn+1)

   MIN=a1^b1*a2^b2*……*an^bn

所以素数不可能放着更小的让它指数为0，去让更大的指数升高，这样一定不是我们要的最优解，pass

所以即使所有素数指数都为1

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 ＞ 2 * 10^9

即an一定小于31

而b1+b2+……+bn<=30

原因也很简单，当素数只有2指数不为0时，指数和最大

有2^31>2e9

即所有素数指数和一定不超过30

这样，我们得出了反素数具备的几个性质

见下方代码头文件前

 1 //反素数y的性质：
 2 //1.y=a1^n1*a2^n2*...*an^nn
 3 // 其中a为素数，n1>=n2>=...>=nn
 4 //2.约数个数(y)=(n1+1)*(n2+2)*...*(nn+1) 
 5 //3.y的质因数指数总和不超过31
 6 //4.y的质因数最大不超过31 
 7 #include <bits/stdc++.h>
 8 using namespace std;
 9 int n;
10 int prime[15]={0,2,3,5,7,11,13,17,19,23,29,31};
11 //所有素数，方便一一枚举 
12 int most=-1;
13 //most表示最大约数个数 
14 long long ans=-1;
15 //ans表示约数最多的数中最小的（符合反素数定义
16 //十年OI一场空，不开long long见祖宗 
17 void dfs(int x,int l,int m,int up){
18 //x表示当前数字大小
19 //l表示当前枚举到的素数约数的下标
20 //m表示x的约数总个数
21 //up表示上一个素数的指数大小 
22     if(m>most||(m==most&&x<ans)){
23     //要么约数更多，要么约数相同但更小 
24         most=m;
25         ans=x;
26     }
27     long long now=x;
28     int i=0;
29     //i表示此素数指数大小 
30     while(i<=up){
31     //反素数性质1，当前素数指数不大于上一素数指数 
32         i++;
33         if(n/now<prime[l])return ;
34         //保证now不超过n 
35         int k=m*(i+1);
36         //反素数性质2，k表示now的约数个数 
37         now*=prime[l];
38         if(now<=n)dfs(now,l+1,k,i);
39     }
40 }
41 int main(){
42     scanf("%d",&n);
43     dfs(1,1,1,31);
44     printf("%d",ans);
45     return 0;
46 } 

蓝题还是很有意思的

//谁掠夺春秋
//谁在大雨之后
//把旗帜插在最高的楼
//执着信念还有谁有
//有谁能坚守
//摇摇欲坠不停退后
//毁灭即拯救
//夏日掠夺春秋
//结局无法看透
//明知城池已失守
//缠绵往复不肯放手

//——极恶都市