It has been 814 days since the last update, the content of the article may be outdated.
C. Interesting Sequence
By xiaruize
思路
手模一下样例一
10=(1010)2 , 发现需要将 21 位的 1 去掉
此时,就需要与一个 21 位为 0 的数, 同时其它位不能使 10 改变, 且这个数 ≥10
那么, 这个数的最小值显然为 (1100)2=12
总结上面的过程, 得到以下这些结论
n&x=x , 否则是 -1
考虑 n−x 的值的二进制表示 (即 n 中需要改为 0 的二进制位的值), 发现所有的 1 必须是 n 中最低且连续的, 否则 -1
设 n−x 中最高位的 1 在 2k 位上, 那么 2k+1 位在 n 中一定为 0 , 否则 -1
否则答案为 2k+1−n+x
samples
- n=11,m=4
- n=20,m=16
- n=11,m=9
如果不能理解结论,建议手模一遍上述样例
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
|
#include <bits/stdc++.h> using namespace std; #define int long long #define ull unsigned long long #define ALL(a) (a).begin(), (a).end() #define pb push_back #define mk make_pair #define pii pair<int, int> #define pis pair<int, string> #define sec second #define fir first #define sz(a) int((a).size()) #define rep(i, x, y) for (int i = x; i <= y; i++) #define repp(i, x, y) for (int i = x; i >= y; i--) #define Yes cout << "Yes" << endl #define YES cout << "YES" << endl #define No cout << "No" << endl #define NO cout << "NO" << endl #define debug(x) cerr << #x << ": " << x << endl #define double long double const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const int N = 2e5 + 10;
int n, x; int t;
void solve() { cin >> n >> x; if (x > n) { cout << "-1" << endl; return; } if (x == n) { cout << n << endl; return; } int p = n - x; int d = p; for (int i = 0; i <= 61; i++) { if (p < 0) { cout << "-1" << endl; return; } if (p == 0 && (n & (1ll << i))) { cout << "-1" << endl; return; } if (p == 0) { cout << (1ll << i) - d + n << endl; return; } if (n & (1ll << i)) { p -= (1ll << i); } } }
signed main() { cin >> t; while (t--) solve(); return 0; }
|