思路
首先我们可以考虑把能分的都先分了，再选择去切剩下的苹果。
那么我们只需要考虑苹果数量少于人数的情况，每个人能分的苹果都必然少于目前的单个苹果，所以每个苹果都必须切一刀，那么答案数就会增加当前的数量，再把能分的都分了，重复这一过程，直到分完为止。这样去切一定是最优的。
那么，什么时候无解呢？
因为如果让苹果数和人数都同时除以某个数时，有没有解应该都一样。
所以可以考虑先除以苹果数和人数的 \(\gcd\)，那么这时，如果人数不是 \(2^k\) 的话，意味着人数拥有某个非二质因子是苹果数没有的，那么无论苹果数怎么平分翻倍，也无法成为人数的倍数，此时无解。
这样的话，对于某个苹果数和人数，人数必然是 \(2^k\)，那么最多进行 \(k\) 次上述操作即可，所以时间复杂度是 \(\log m\)，完全可以接受。
AC code
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,ans;
inline int lowbit(int x){return x&(-x);}//用于判断是否是二的幂
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
if(lowbit(m/__gcd(n,m))!=m/__gcd(n,m)){printf("-1\n");continue;}//判断无解
ans=0,n%=m;
while(n) ans+=n,n*=2,n%=m;//模拟操作
printf("%lld\n",ans);
}
return 0;
}