题目描述

难度分:$1400$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。

每组数据输入$n(1 \leq n \leq 10^9)$和$m(1 \leq m \leq 10^9)$。

你有$n$个一样的苹果，要均分给$m$个小朋友，每个小朋友分到的量必须是一样的。

每次操作，你可以把一个苹果切开，得到两个一样的苹果块；或者，把一个苹果块一分为二，得到两个更小的苹果块。

你最少要操作多少次？如果无法做到，输出$-1$。

输入样例

4
10 5
1 5
10 4
3 4

输出样例

0
-1
2
5

算法

数学

由于每次操作都只能让所得苹果的重量增加$\frac{1}{2^x}$，因此$\frac{n}{m}$的最简分式的分母一定是$2$的次幂，不是就肯定无解。

下面考虑有解的情况，首先把$n$个苹果每个人分$\lfloor \frac{n}{m} \rfloor$个（$\lfloor . \rfloor$表示对$.$向下取整，这个就是每个人分到的整苹果数，除了分出去的整苹果，剩下的苹果分到每个人手上都不是完整的），$n$个苹果就只剩下$n \% m$个，将$n$更新为这个余数。

此时问题就相当于把剩下的$n$个苹果又均分给$m$个人，先每个切一刀，操作数增加$n$，然后苹果的块数会变为原来的两倍即$2n$。这时候问题就转变为将$2n$个苹果平均分配给$m$，相当于出现子问题，又分出去$m$块，让$2n$对$m$取模更新成新的$n$（剩下$2n \% m$）。如此反复直到$n$变成$0$，停止操作。

复杂度分析

时间复杂度

算法过程中$n$需要反复对$m$取模，因此时间复杂度大概就是$O(log_mn)$级别。

空间复杂度

整个算法用迭代实现，仅使用了有限的几个变量，额外空间复杂度为$O(1)$。

$python$ 代码

from math import gcd

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    g = gcd(n, m)
    x = m // g
    if x == (x&-x):
        cur = n // m
        n = n % m
        ans = 0
        while n > 0:
            ans += n
            n = n * 2 % m
        print(ans)
    else:
        print(-1)