我们可以强行拆一下柿子，最终得到的值会是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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           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
           
            =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
            
             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