web analytics

分火腿 数学

题目描述:

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

输入描述:

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

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

输出描述:

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

样例输入:

2

2 6

6 2

样例输出:

4

0

数据范围:

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

分析:

这道题其实就是一道公式题.

我们重复一下题目.可以发现题目讲的是:

我们有n长度分成m  所以我们可以知道每块长度为\frac{n}{m}

之后我们已知每长度为1时就不需要切.

所以我们需要求出 1 与\frac{n}{m}的最小公倍数 = 两数乘积除GCD.

其实就是

 \frac{ \frac{n\cdot m }{gcd(n,m)} }{m} = \frac{n}{gcd(n,m)}

所以我们可以少切的就是n除以 它们的最小公倍数 然后减1.(因为最后一块其实我们是不需要切的然而我们是算进去的.所以这个需要处理.

 \frac{n}{ \frac{n}{gcd(n,m)} } = gcd(n,m)-1

所以这样处理一下就好了.

 

 

Post a Comment

You must be logged in to post a comment.