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();

}