考虑先进行除以 $2$ 操作, 将 $a$ 中的数字化为奇数.
然后依次考虑集合 $b$ 中的数字.
如果没有出现再 $a$ 中, 就除以 $2$ , 直到变为 $1$ , 如果还没有出现在集合 $a$ 中, 那么无解.
正确性:
首先将 $a$ 中所有的数, 变为最小基数, 也就是通过不断乘以 $2$ 可以还原回来的最大奇数.
依次考虑集合 $b$ 中的每一个数字, 如果不能对应到 $a$ 中的某一个数字, 那么就是无解.
Code
#include <algorithm>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
void solve() {
int n;
cin >> n;
multiset<int> a, b;
for (int i = 0; i < n; i ++ ) {
int x;
cin >> x;
while (x % 2 == 0) {
x /= 2;
}
a.insert(x);
}
for (int i = 0; i < n; i ++ ) {
int x;
cin >> x;
b.insert(x);
}
for (auto it = b.begin(); it != b.end(); it ++ ) {
int x = *it;
if (a.find(x) != a.end()) {
a.extract(x);
} else {
bool ok = false;
while (x > 1) {
x /= 2;
if (a.find(x) != a.end()) {
a.extract(x);
ok = true;
break;
}
}
if (!ok) {
cout << "NO" << '\n';
return;
}
}
}
assert(a.size() == 0);
cout << "YES" << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt -- ) {
solve();
}
return 0;
}