我们可以强行拆一下柿子，最终得到的值会是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>=10)write(x/10); putchar(x%10+'0'); } LL a,b,p,q,l,r; LL mi[110]; LL now,nt,np,psd[110000]; LL u[110]; void pro(LL k) { np=0; if(k==0){psd[++np]=u[0],nt=0;return ;} if(u[0]!=0) nt=0,psd[++np]=u[0]; else nt=1; psd[++np]=1; for(LL i=1;i<k;i++) { if(u[i]==0)psd[np]++; else psd[++np]=u[i],psd[++np]=1; } if(u[k]!=0)psd[++np]=u[k]; reverse(psd+1,psd+np+1); nt=(nt+np+1)%2; } bool calc(LL k) { LL x=mi[k]*p,y=mi[k]*q; now=k; memset(u,0,sizeof(u)); if(x>=l){pro(k);return true;} for(LL i=k;i>=0;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]+1)*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[110000]; bool smaller() { if(ans==-1||ans>now)return true; else if(ans<now)return false; if(nt<ft)return true; else if(nt>ft)return false; for(int i=1;i<=now;i++) if(psd[i]!=num[i])return ((i+nt)%2==1)^(psd[i]>num[i]); } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int T_T=0; while(scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&p,&q,&l,&r)!=EOF) { if(a==0&&b==0&&p==0&&q==0&&l==0&&r==0)break; printf("Case %d: ",++T_T); if(l<=p&&q<=r){puts("empty");continue;} ans=-1;mi[0]=1; for(LL k=0;mi[k]*q<=r;k++) { if(mi[k]*q-mi[k]*p+1>r-l+1)break; if(calc(k)) { if(smaller()) {ans=now,ft=nt,tp=np;memcpy(num,psd,sizeof(num));} } mi[k+1]=mi[k]*b; if(b==1)break; } if(ans==-1){puts("impossible");} else { for(LL i=1;i<tp;i++) write(num[i]),putchar(((i+ft)%2==1)?'A':'M'),putchar(' '); write(num[tp]),putchar(((tp+ft)%2==1)?'A':'M'),puts(""); } } return 0; }