题目描述

小月言要过四岁生日了, 她的妈妈为她准备了 n 根火腿, 她想将这些火腿均分给 m 位小朋友, 所以她可能需要切火腿. 为了省事, 小月言想切最少的刀数, 使这 n 根火腿分成均等的 m 份. 请问最少要切几刀?

输入描述

第一行一个整数 T, 表示有 T 组数据.

接下来 T 组数据, 每组共一行, 有两个数字 n, m.

输出描述

每组数据一行, 输出最少要切的刀数.

样例输入

2
2 6
6 2

样例输出

4
0

数据范围

100% 的数据保证 \(T \leq 1000\);\(n, m \leq 2147483647\).

Explanation

大概这样想, 先把所有人数、火腿除以两者的最大公约数使其互质.

然后就变成了一个很和谐的问题.

如果 \(n\) 比 \(m\) 小, 则很显然会切 \(m - 1\) 刀.

如果 \(n\) 比 \(m\) 大, 则很显然会切 \(m - 1\) 刀.

这样显然总是会切 \(m - 1\) 刀, 当然此时必须有 \(gcd(n, m) = 0\).

反过来想, 把 \(m - 1\) 乘回去, 就有了 \(m - gcd(n, m)\).

然后就是一道水题了

Example Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

int T, n, m;

int gcd(int x, int y)
{
    if (y == 0) return x;
    return gcd(y, x % y);
}

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d", &n, &m);
        int res = m - gcd(n, m);
        printf("%d\n", res);
    }
    return 0;
}