首页 > 代码库 > 分火腿

分火腿

分火腿

(hdogs.pas/.c/.cpp)

时间限制:1s;空间限制 64MB

题目描述:

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

输入描述:

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

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

输出描述:

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

样例输入:

3

2 6

3 4

6 2

样例输出:

4

3

0

数据范围:

100%的数据保证T<=1000;n,m<=2147483647。

【题目分析】

    这题就是找规律呀,反正我是这么搞的,数据类型...int就可以

#include<cstdio>#include<iostream>#include<cstring>using namespace std;int t;long long n,m;long long ans;int gcd(int x,int y){    if(y==0) return x;        if(x<y) return gcd(y,x);        else return gcd(y,x%y); }int main(){    freopen("hdogs.in","r",stdin);    freopen("hdogs.out","w",stdout);    scanf("%d",&t);    while(t--)    {        scanf("%lld%lld",&n,&m);        if(n%m==0)            ans=0;        else if(m%n==0)            ans=n*(m/n-1);        else             ans=m-gcd(n,m);        printf("%lld\n",ans);    }    fclose(stdin);fclose(stdout);    return 0;}

 

分火腿