Codeforces Round 901 (Div. 2) C. Jellyfish and Green Apple （位运算）

Codeforces Round 901 (Div. 2) C. Jellyfish and Green Apple

//思路：浮点数转二进制，a/b的结果为  gcd（a，b）*最简分式（n/m）的结果
//苹果能分的前提是人数得是一个2的次幂数，通过切割只能分为形同0.001的二进制小数
//a/b的二进制如果在从左到右的sp位为 1 ，则需要切割到这个情况
//一个苹果切割到这一位共用 2^(sp-1)-1 刀 ， 得到 2^(sp) 份这样的苹果
//则要加上 (m /(1 << sp)) * ((1 << sp) - 1) 刀
//结果乘上先前优化的gcd

#define int long long
#define ld long double

using namespace std;

int gcd(int a, int b)
{
	if (b)return gcd(b, a % b);
	else return a;
}

void op()
{
	int n, m;
	cin >> n >> m;

	if (n % m == 0)cout << 0 << endl;
	else
	{
		int tmp = m;
		int k = gcd(n, m);
		n /= k;
		m /= k;

		if (m % 2)
		{
			cout << -1 << endl;;
			return;
			
		}
		int fg = 0;

		int kk = m;
		while (kk)
		{
			if (kk & 1)fg++;
			kk >>= 1;
			if (fg > 1)
			{
				cout << -1 << endl;
				return;
			}
		}

		bool st = true;
		int sp = 1,ans=0;

		while (st&&sp<=33)
		{
			if (((n << sp)/m) & 1)
			{
				ans += (m / ((int)1 << sp)) * (((int)1 << sp) - 1);
			}
			if ((n << sp) % m == 0)
			{
				st = false;
			}
			sp++;
		}

		cout << ans * k << endl;
	}
}

signed main()
{
	int t;
	cin >> t;
	while (t--)op();

	return 0;

}