分火腿
题目描述：
小月言要过四岁生日了，她的妈妈为她准备了n根火腿，她想将这些火腿均分给m位小朋友，所以她可能需要切火腿。为了省事，小月言想切最少的刀数，使这n根火腿分成均等的m份。请问最少要切几刀？
输入描述：
第一行一个整数T，表示有T组数据。
接下来T组数据，每组共一行，有两个数字n，m。
输出描述：
每组数据一行，输出最少要切的刀数。
样例输入：
2
2 6
6 2
样例输出：
4
0
数据范围：
100%的数据保证T<=1000；n,m<=2147483647。
蒟蒻吐槽：
一道奇奇怪怪的数学题吧？貌似。题目可以分为两种情况，n>m或者n<m，但其实，在n>m的情况中，把多余的火腿直接整个分给其他人就可以了。所以n-=n/m*m。然后就变成了n<m的情况了。在n<m中，可以把n根火腿看成一根大火腿，在1/n.2/n,3/n···
n-1/n处已经被切过了，而为了平均分配，我们要在1/m,2/m,3/m···m-1/m处再次切割，所以我们只需要求二者交集，交集是我们可以偷懒的刀数，而我们总共要砍m-1刀。
以上就是对这道题的感性认知。
重要的理性思维到来了！虽然很烦，但这是历史的必然啊！已经被切过的刀位置定义为p/n，需要的刀定义为q/m。通分得pm/mn和qn/mn，二者交集等价于pm=qn，从p=n，q=m出发易得p，q同时除以gcd（m，n）后，等式才可以继续成立，又因为p和q中较小的是p所以交集个数受n限制，即个数=（n-1）/gcd（n，m）。为什么要减一呢？注意了，p<=n-1所以ans=m-1-（n-1）/gcd（n，m）。顺便附上代码。
代码
#include<cstdio> int gcd(int a,int b) { int r=a%b; while(r!=0) { a=b; b=r; r=a%b; } return b; } int main() { freopen("hdogs.in","r",stdin); freopen("hdogs.out","w",stdout); int T,a,b,x,ans; scanf("%d",&T); while(T--) { scanf("%d%d",&a,&b); if(a%b==0){printf("0\n");continue;} a=a-b*(a/b); x=gcd(a,b); x=a/x; ans=b-1-(a-1)/x; printf("%d\n",ans); } return 0; }
