解题思路

题目给定两个长度为 $n$ 的正整数数组 $a,b$。

一次操作中，可以在数组 $a$ 中选出若干个当前数值相同的元素，并把它们同时乘 $2$。目标是用最少操作次数，让 $a$ 和 $b$ 的元素多重集合完全相同，顺序无关；如果无法实现，输出 $-1$。

核心思路

一个数在不断乘 $2$ 的过程中，它的“奇数部分”永远不会改变。

题目内容

在神秘的魔法工坊中，小美有两个魔法阵列 $a$ 和$b$，长度均为 $n$。在一次操作中，她可以在 $a$ 中选择若干个值相同的元素，并将它们的值同时翻倍一次（即乘以 $2$）。

小美希望通过若干次操作，使阵列 $a$ 的元素多重集合与阵列 $b$ 完全一致（不要求顺序，只关心元素及其出现次数）。

请计算将 $a$ 变换为 $b$ 的元素多重集合所需的最小操作次数；如果无法实现，则输出 $-1$。

输入描述

• 第一行输入一个整数 $T(1≤T≤10^5)$，表示测试数据组数。

• 每组测试数据描述如下：

  • 第一行输入一个整数$n(1≤n≤10^5)$，表示数组长度。
  • 第二行输入 $n$个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$，表示初始数组 $a$。
  • 第三行输入 $n$个整数 $b_1,b_2,…,b_n(1≤b_i≤10^9)$，表示目标数组 $b$。

保证所有测试用例中$n$ 的总和不超过$5×10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示将 $a$ 转换为与 $b$ 元素多重集合相同所需的最小操作次数；如果无法实现，则输出 $-1$。

样例1

输入

3
3
1 2 3
2 4 3
4
1 1 2 2
4 2 2 1
2
3 5
3 9

输出

2
2
-1

说明

样例一:{$1,2,3$}$\rightarrow${$2,4,3$},先将$1\rightarrow 2$, 再将$2\rightarrow 4$,共$2$步。

样例二:{$1,1,2,2$}$\rightarrow${$4,2,2,1$}。可对一个$1$倍化一次对一个$2$倍化一次，最少$2$步。

样例三:$9$不是$5×2^k$ 的形式，故无解，输出$-1$。