Codeforces Round #735 (Div. 2) C. Mikasa
ps:代码最后调出来来不及交了,没有AC,纯属口嗨 qwq
本质是找个最小的k使得n^k>m
\(n > m\) 则答案为0
下面描述的变化量即为要找的k。
1、找到n最高的值为1且不与m相同的一个二进制位,假设为第x位,代表的值为2^(x-1)
2、若能找到这样的二进制位,因为要使n^k>m,那么n高于该位的值为0的位都应该向m补齐(补齐,即若m此位为1,n此位为0,则应该补为1),低于该位的不做处理(保证n的变化量,即k尽量小)。
3、若找不到这样的二进制位,那么可以以最低的代价造一个这样的二进制位(即找到m的二进制值为0的最低位,把n对应位置变成1),然后再按照上面处理。
明天再交代码试试。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;
LL n, m;
//找二进制为0的最低位
LL ct(LL x) {
LL res = 1;
while(true) {
if ((x & res) == 0) return res;
res <<= 1;
}
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%lld%lld", &n, &m);
if (n > m) {
printf("0\n");
continue;
}
//找x代表的值
LL tmp = 1, last = -1;
while(tmp <= n) {
if ((n & tmp) != 0 && (m & tmp) == 0) {
last = tmp;
}
tmp <<= 1;
}
LL p = ct(m);
if (last == -1) {
printf("%lld\n", m+p-n-(m%p)+(n%p));
} else {
printf("%lld\n", m-(m%last)-(n-(n%last)-last));
}
}
}