分析
- 先掏出式子
可以发现,如果确定了 的值,那么z的合法范围就可以求出来,并且 ,完全可以 枚举。接下来考虑右边的括号。首先我们已经有了z的范围[1,max],如果k第i位为1,那么z的第i位在满足 的条件下也得为1,这样原式相当于就会减小 ,如果k这一位为0,z这一位也应为0,因为如果为1,根据异或的性质,前面的异或结果会增加 ,而后面的会减少 ,什么也没变,但是我z却变大了,不就亏了吗。
代码
/* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=1e5+10; ll n,st,d,k,ma; ll a[N],b[N]; int main() { scanf("%lld%lld%lld%lld%lld",&n,&st,&d,&k,&ma); for (ll i=1;i<=n;i++) a[i]=st+(i-1ll)*d,b[i]=b[i-1]+a[i]; ll ans=(1ll<<62); for (ll i=1;i<=n;i++) {//枚举r-l+1 ll l=0,r=a[n-i+1],z=-1; while(l<=r) { ll mid=(l+r)/2; ll now=b[n-i]+i*mid; if(now<=ma) z=mid,l=mid+1; else r=mid-1; }//找到z的最大值 if(z<0) continue; ll las=0; for (ll j=40;j>=0;j--) if((k>>j)&1) { ll ok=(1ll<<j)+las; if(ok<=z) las=ok; } ans=min(ans,i*((las^k)+k-las)); } if(b[n]<=ma) ans=0; printf("%lld\n",ans); return 0; }