bzoj3957: [WF2011]To Add or to Multiply

gay队牛逼！

我们可以强行拆一下柿子，最终得到的值会是m^k*x+m^k*u(k)*a+m^k-1*u(k-1)*a……m^0*u(0)*a

其中u表示后面有i个m的a有多少个

答案就是k+∑u

枚举每一个k，然后贪心选择u(k)，那么k越大u(k)也尽可能取大，答案才会越小

其实想过拆柿子的啊，但是有些u=0我把这些位给忽略掉啦，搞得不是很会

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

inline LL write(LL x)

{

    if(x>=)write(x/);

    putchar(x%+'');

}

LL a,b,p,q,l,r;

LL mi[];

LL now,nt,np,psd[];

LL u[];

void pro(LL k)

{

    np=;

    if(k==){psd[++np]=u[],nt=;return ;}

    if(u[]!=)

        nt=,psd[++np]=u[];

    else nt=;

    psd[++np]=;

    for(LL i=;i<k;i++)

    {

        if(u[i]==)psd[np]++;

        else psd[++np]=u[i],psd[++np]=;

    }

    if(u[k]!=)psd[++np]=u[k];

    reverse(psd+,psd+np+);

    nt=(nt+np+)%;

}

bool calc(LL k)

{

    LL x=mi[k]*p,y=mi[k]*q; now=k;

    memset(u,,sizeof(u));

    if(x>=l){pro(k);return true;}

    for(LL i=k;i>=;i--)

    {

        LL d=l-x;

        u[i]=d/a/mi[i];

        if(x+mi[i]*u[i]*a>=l){now+=u[i];pro(k);return true;}

        else if(y+mi[i]*(u[i]+)*a<=r){now+=++u[i];pro(k);return true;}

        else

        {

            now+=u[i];

            x+=mi[i]*u[i]*a;

            y+=mi[i]*u[i]*a;

        }

    }

    return false;

}

LL ans,ft,tp,num[];

bool smaller()

{

    if(ans==-||ans>now)return true;

    else if(ans<now)return false;

    if(nt<ft)return true;

    else if(nt>ft)return false;

    for(int i=;i<=now;i++)

        if(psd[i]!=num[i])return ((i+nt)%==)^(psd[i]>num[i]);

}

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    int T_T=;

    while(scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&p,&q,&l,&r)!=EOF)

    {

        if(a==&&b==&&p==&&q==&&l==&&r==)break;

        printf("Case %d: ",++T_T);

        if(l<=p&&q<=r){puts("empty");continue;}

        ans=-;mi[]=;

        for(LL k=;mi[k]*q<=r;k++)

        {

            if(mi[k]*q-mi[k]*p+>r-l+)break;

            if(calc(k))

            {

                if(smaller())

                    {ans=now,ft=nt,tp=np;memcpy(num,psd,sizeof(num));}

            }

            mi[k+]=mi[k]*b;

            if(b==)break;

        }

        if(ans==-){puts("impossible");}

        else

        {

            for(LL i=;i<tp;i++)

                write(num[i]),putchar(((i+ft)%==)?'A':'M'),putchar(' ');

            write(num[tp]),putchar(((tp+ft)%==)?'A':'M'),puts("");

        }

    }

    return ;

}