题解 P1463 【[HAOI2007]反素数】
这篇题解之前的一些题解的优化：
1、指数单调不增；
2、用前k个质数搜索。
我们来加两个优化把它优化到0ms.
显然，我们要限制每个质数的指数。
对于3，5，7...(这个质数设为p)的指数(设为q)(假设2的指数为q1,下文同上)：
设K(p) = 最小的使2^k(2的k次方)大于p的数字k。
则：2^k > p , 2^(k-1) < p
( 2^q1 )( p^q ) > ( 2^(q1+k-1) ) ( p^(q-1) )
我们要求反质数，所以：
(q1+1)(q+1) < q(q1+k)
化简得到：q < (q+1) / (k-1) [ 注意：这里不是整数除法！！！ ]
就可以限制除了2之外所有质数的指数了。
OK！
那么对于2：
我们设k , ....(见上文,其中的p改为不出现在反质数中的质因数的质数)
则：
2^q1 > 2^(q1-k) * p
我们要求反质数，所以：
q1+1 > (q1-k+1) * 2
化简得：
q1 < 2K-1.
于是我们就有了两个强大的剪枝条件。
0msAC代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read(){
LL x = 0,f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
while (c <='9' && c >='0') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
inline void write(LL x){
LL k = 0,lx = x;char put[40];
if (lx ==0) putchar('0');
if (lx < 0) putchar('-'),lx = -lx;
while (lx) put[++k] = (lx % 10) + '0',lx /= 10;
while (k) putchar( put[ k-- ] );
putchar('\n');
}
int K(int x){//K()函数
int ans = 0;
for (ans = 0; (1<<ans) <= x; ++ans) ;
return ans;
}
LL n,ans,mxtot;
const int p[16] = {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int limit_p[16],p1;
void dfs(LL i,LL tot,LL now,LL mxw){
if (now > n) return;
if (i>1){ //limit_p[i] = (long double)1.0 * (p1+1) / (K(p[i]) - 1);
if ((p1+1) % (K(p[i]) - 1)) limit_p[i] = (p1+1) / (K(p[i]) - 1) + 1;
else limit_p[i] = (p1+1) / (K(p[i]) - 1);
}//算出当前的指数限制
LL num = now * p[i],w = 1,ntot = tot;
while (num <= n && w <= mxw && w < limit_p[i]){
ntot = tot * (w + 1);
if (ntot > mxtot) mxtot = ntot,ans = num;
if (ntot == mxtot && num < ans) ans = num;
if (i == 1) p1 = w;//记录p1
dfs(i+1,ntot,num,w);
num *= p[i],++w;
}
}
void work(){//求出p1的限制
long long x = 1,t = 0;
for (int i = 1; i <= 15 && x <= n; ++i) x *= p[i],t = i;
t = K( p[t] ) * 2 - 1;
limit_p[1] = t;
}
int main(){
n = read();
if (n == 1) {//特判（我也不知道这东西有什么用）
cout << 1 << endl;
return 0;
}
ans = 1; mxtot = 1;
work();//求出p1的限制
dfs(1,1,1,20);//搜索
write(ans);
return 0;
}