【NOIP模拟赛】分火腿

2014年10月24日8360

题目描述:

小月言要过四岁生日了,她的妈妈为她准备了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

每段长度为n/m,需要切m-1次,k*lcm(n/m,1)的断点不需要代价

lcm(n/m,1)=lcm(n,m)/m=nm/(gcd(n,m)*m)=n/gcd(n,m)

k共有n/lcm(n/m,1)-1=gcd(n,m)-1个,所以最终要切m-gcd(n,m)次

我的理解

比如n根火腿切m份,每一份长n/m,我们发现对于 n/m * K 为整数的情况,就不用刀子切

答案就是

\[m-\sum_{k=1}^{m}(\frac{n}{m}*k\in Z?)\]

约分

\[m-\sum_{k=1}^{m}(\frac{n/(n,m)}{m/(n,m)}*k\in Z?)\]

\[m-\sum_{k=1}^{m}((m/(n,m))|k?)\]

\[m-m/(m/(n,m))\]

\[m-(n,m)\]