BZOJ 3085: 反质数加强版SAPGAP （反素数搜索）

题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3085

题意：求n(<=10^100)之内最大的反素数。

思路：

优化2：

 

int prime[]=
{1,  2,  3,  5,  7,11, 13, 17, 19, 23,29, 31, 37, 41, 43,47, 53, 59, 61, 67,71, 73, 79, 83, 89,97, 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251
};
int K[]=
{1,2,2,3,3,4,4,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
};
struct BIGINT
{int a[27];BIGINT(){}BIGINT(char *s){clr(a,0);int i,L=strlen(s),cur=0;for(i=L-1;i-3>=0;i-=4){a[cur]=(s[i-3]-'0')*1000+(s[i-2]-'0')*100+(s[i-1]-'0')*10+(s[i]-'0');cur++;}if(i<0) return;if(i==0) a[cur]=s[0]-'0';else if(i==1) a[cur]=10*(s[0]-'0')+(s[1]-'0');else if(i==2) a[cur]=100*(s[0]-'0')+10*(s[1]-'0')+(s[2]-'0');}BIGINT(int x){clr(a,0);a[0]=x;}inline BIGINT operator*(int x){int i;BIGINT tmp;for(i=0;i<27;i++) tmp.a[i]=a[i]*x;for(i=0;i<26;i++){tmp.a[i+1]+=tmp.a[i]/10000;tmp.a[i]%=10000;}return tmp;}int operator<(BIGINT p){int i;for(i=26;i>=0;i--){if(a[i]p.a[i]) return 0;}return 0;}int operator==(BIGINT p){int i;for(i=26;i>=0;i--){if(a[i]!=p.a[i]) return 0;}return 1;}int operator<=(BIGINT p){return *this==p||*this0&&0==a[cur]) cur--;printf("%d",a[cur]);cur--;while(cur>=0) printf("%04d",a[cur--]);puts("");}
};char s[111];
BIGINT n;
int Max;int cnt2;BIGINT ans;
i64 ansFac;void DFS(int dep,BIGINT cur,i64 facNum,int preMax)
{if(facNum>ansFac||facNum==ansFac&&cur1) Min=min(Min,cnt2/(K[dep]-1));for(i=1;i<=Min;i++){if(dep==1) cnt2=i;cur=cur*prime[dep];tmp+=facNum;if(n