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 1;
            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||*this<p;
    }

    void print()
    {
        int cur=26;
        while(cur>0&&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&&cur<ans)
    {
        ans=cur;
        ansFac=facNum;
    }
    int i;
    i64 tmp=facNum;
    int Min=min(preMax,2*K[Max]-1-1);
    if(dep>1) 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<cur) break;
        DFS(dep+1,cur,tmp,i);
    }
}

int main()
{

    scanf("%s",s);
    n=BIGINT(s);

    if(n==BIGINT(1))
    {
        puts("1");
        return 0;
    }
    BIGINT cur=BIGINT(1);
    while(cur<=n) cur=cur*prime[++Max];
    DFS(1,BIGINT(1),1,100);
    ans.print();
}