首页 > 代码库 > 分火腿
分火腿
分火腿
（hdogs.pas/.c/.cpp）
时间限制：1s；内存限制 64MB
题目描述：
小月言要过四岁生日了，她的妈妈为她准备了n根火腿，她想将这些火腿均分给m位小朋友，所以她可能需要切火腿。为了省事，小月言想切最少的刀数，使这n根火腿分成均等的m份。请问最少要切几刀？
输入描述：
第一行一个整数T，表示有T组数据。
接下来T组数据，每组共一行，有两个数字n，m。
输出描述：
每组数据一行，输出最少要切的刀数。
样例输入：
2
2 6
6 2
样例输出：
4
0
数据范围：
100%的数据保证T<=1000；n,m<=2147483647。
/*可以把n根火腿肠连起来，那么最多需要切m-1刀，如果下刀处恰好是火腿的连接处，那么就少切一刀。最少需要切0刀（n是m的倍数）所以，ans=max(m-gcd(n,m),0);*/#include<cstdio>#include<iostream>using namespace std;int n,m,T;int read(){ int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x;}int gcd(int x,int y){return y==0?x:gcd(y,x%y);}int main(){ freopen("hdogs.in","r",stdin); freopen("hdogs.out","w",stdout); T=read(); while(T--) { n=read();m=read(); printf("%d\n",max(m-gcd(n,m),0)); } return 0;}
分火腿
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。