SSLOJ·分火腿【模拟】

Description–

---

Sample Input–

2
2 6
6 2

Sample Output–

4
0

---

解题思路–

设每根火腿有m片，则一共有n * m片，每份有n片

---

代码–

#include <iostream>
#include <cstdio>
#define ll long long

using namespace std;

ll t, o, f, n, m, g, an, ans;

ll gbs(ll x, ll y)
{
	if (x < y) swap(x, y);
	for (ll i = x; i <= x * y; i += x)
	  if (i % y == 0)
	    return i;
}

void work()
{
	scanf("%lld%lld", &n, &m);
	if (n % m == 0)
	{
		printf("0\n"); //不用切
		return ;
	}
	if (m % n == 0)
	{
		printf("%lld\n", (m / n - 1) * n);
		return ;
	}
	o = m / n;
	f = m % n;
	g = gbs(f, n);
	an = (g / f) * o + g / n;
	ans = ((g / f) * o + (g / n - 1)) * (m / an);
	printf("%lld\n", ans);
}

int main()
{
	scanf("%lld", &t);
	for (ll i = 1; i <= t; ++i)
	  work();
	
	return 0;
}