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

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

 

 

25 Trackbacks

  1. By nancydeckard on 五月 4, 2018 at 3:58 下午

    nancydeckard

    nike roshe run mens boots,nike lunarglide 7 blue orange,new balance 574 blue,nike air max 90 gold purple,nike zoom pegasus 33 black white,air max plus gold metallic

  2. By rx3wvk23 on 五月 14, 2018 at 3:11 下午

    rx3wvk23

    adidas harden blanc rouge,nike lebron 13 orange blue,nike air max 90 ultra se olive,nike kd 9 blu,maschio nike zoom pegasus 32 tutti blu,zapatillas nike dunk sky hi premium,nike free 3.0 trainer black,adidas nmd runner womens grey movie

  3. By flyknit trainer volt grey or gray on 五月 15, 2018 at 3:48 下午

    flyknit trainer volt grey or gray

    asics gel quantum 360 white kitair max 2017 black and purple kushnike air max tavas leather mens shoeasics onitsuka tiger mexico 66 deep navy credit union

  4. By capecodmag on 五月 18, 2018 at 11:04 下午

    capecodmag

    nike air max classic bw id,adidas predator soccer gold red,nike air presto premium maroon,air jordan 31 michigan shoes,nike internationalist black femme,air max 90 se

  5. By buddyspeaker on 五月 19, 2018 at 6:30 下午

    buddyspeaker

    nike internationalist womens red,womens nike internationalist pink green,womens asics gel noosa tri 10 khaki,nike roshe run high black,curry 3 light blue suit,adidas porsche design bounce china

  6. By ugg bailey button leopard print boot warranty on 五月 20, 2018 at 4:50 上午

    ugg bailey button leopard print boot warranty

    adidas forum mid han solo vertenike air max 90 s酶lv r酶dugg leopard bailey bow bootsuggs 5800 for sale los angeles

  7. By nike lunarglide 7 images salon on 五月 24, 2018 at 3:16 上午

    nike lunarglide 7 images salon

    disney park exclusive pandora charms 2016wholesale pandora charms spacers stoppercheap pandora beads polarischeap cheap pandora necklace

  8. By ugg classic short sparkles boots quality for sale on 五月 25, 2018 at 7:53 上午

    ugg classic short sparkles boots quality for sale

    ray ban clubmaster frame only for salewholesale oakley crankcase purplecheap oakley garage rock salewholesale ray ban metal clubmaster

  9. By air max 1 ultra moire wolf grey white on 五月 25, 2018 at 8:45 上午

    air max 1 ultra moire wolf grey white

    reebok gl 6000 womankd 8 blue and white for saleair max 1 black white and greynike zoom kobe 9 low em portugues

  10. By canada goose kensington parka australia live on 五月 25, 2018 at 2:30 下午

    canada goose kensington parka australia live

    coach messenger bags for cheap zombiescoach ashley hippie crossbody bagdiscount jimmy choo discountwholesale manolo blahnik hangisi flats price

  11. By artkabis on 五月 26, 2018 at 6:32 上午

    artkabis

    nike air huarache silver snakeskin,nike air max 90 sneakerboot romania pret,o nike shox r4 superfly,adidas zx 850 green sky blue,nike air max 95 sneakerboot green,nike air max plus powder blue

  12. By mens nike zoom pegasus 33 blue grey on 五月 28, 2018 at 2:26 上午

    mens nike zoom pegasus 33 blue grey

    nike kobe 11 femmes vert noirlunarglide 7 grigio hairnike air max tn l酶ping sko grayugg boots mini bailey button dry leaf leafy greens

  13. By 匿名 on 五月 28, 2018 at 4:55 上午

    north face apex bionic jacket temperature rating guide

  14. By air jordan 4 retro yellow black used on 六月 1, 2018 at 2:17 上午

    air jordan 4 retro yellow black used

    nike air max 95 invigor print red black mens classic nike air max 95 black red mens jogging shoesnike flyknit roshe run nm qs multicolor quartznike free 3.0 flyknit 2015 womens shoesadidas tubular runner heather grey epub

  15. By womens nike dunk sky high 2.0 on 六月 3, 2018 at 1:14 上午

    womens nike dunk sky high 2.0

    nike kobe red black,asics gel quantum 360 womens 2017 black,nike free 5.0 cool grey,nike lunartempo id,womens asics gel noosa tri 7 pink orange,nike vapormax nero,air jordan retro 9 grau minzgrün,nike zoom kobe vi black

  16. By seldongill on 六月 4, 2018 at 4:53 上午

    seldongill

    nike air max plus lava red for sale,jordan 6 painted galaxy 7,nike air force 1 zipper suede,bon marché nike sb blazer low femmes orange,womens nike huarache ultra all black,nike air max plus collection,nike air force 1 hi dcn military boot mens shoe,ni…

  17. By pcmilampung on 六月 5, 2018 at 8:30 上午

    pcmilampung

    womens nike free 3.0 v5 ext orange red red running shoes on sale,nike air max zero qs gold medal 789695 700,ef177 nike air max tn shoes white metallic gold yellow black mens,womens nike free rn black and gold shoes,nike air classic bw red black white c…

  18. By cheap pandora charms japan price on 六月 5, 2018 at 2:05 下午

    cheap pandora charms japan price

    cheap moncler jackets warm glovesmoncler vests womens yoga atlanta for salemoncler quilted jacket sale philippinesmoncler down coats uk jacket for sale

  19. By ugg bailey button triplet metallic grey eyes on 六月 5, 2018 at 5:47 下午

    ugg bailey button triplet metallic grey eyes

    michael kors essex shoulder bag jdmoncler vest mens sale mens for salemoncler jackets worth it vinemoncler mens vests quest not working

  20. By cheap pandora charms cyber monday deals on 六月 6, 2018 at 10:41 上午

    cheap pandora charms cyber monday deals

    ugg classic mini floral grunge womens chestnut oilugg boots australia bailey button chestnutugg australia mini bailey button perla meaningclassic tall uggs uk

  21. By reebok gl 6000 navy green gold on 六月 7, 2018 at 5:59 上午

    reebok gl 6000 navy green gold

    nike kobe 11 white horse mp3,nike dunk sb 2016,nike zoom pegasus 33 gold pink,nike hypervenom phatal 3 df fg firm ground soccer cleat,air jordan 11 retro bred,adidas ultra boost negro negro

  22. By 2g9s16lv on 六月 7, 2018 at 7:13 上午

    2g9s16lv

    nike shox kaufen schweiz,nike free hyperko shield trainer uk,womens nike air max command purple,nike air max command leder trainers,adidas zx flux czarne 42 5,nike air max 90 em hvit gull,nike air huarache sky blue,nike air force 1 lunar duckboot

  23. By nike air max 2016 triple black on 七月 2, 2018 at 5:07 上午

    nike air max 2016 triple black

    mens asics asics gel kayano 20 red black,nike zoom pegasus 33 zoom pegasus 33 black,nike juvenate team red,nike air max 90 ultra se cargo khaki,jordan mens black cat mid molded baseball cleat want need,2017 nike kyrie 3 mountain dew k.a.r.e. white gree…

  24. By ppfbfq42 on 七月 3, 2018 at 6:34 上午

    ppfbfq42

    air jordan reveal grey gold,nike womens roshe run high sneakerboot,yeezy boost 950 wine,jordan retro 12 dark bleu,nike internationalist black suede,nike zoom pegasus 31 himmelblau silber,adidas superstar anniversary,mens air jordan 13 retro flint 2010…

  25. By nike tiempo legend x bape on 七月 15, 2018 at 4:17 下午

    nike tiempo legend x bape

    nike air max 97 red grey,air jordan retro 11 royal blue silver,nike hyperdunk all white purple,nike dunks wedges,nike air force 1 foamposite pro low anthracite black,nike shox turbo vi sl black,nike cortez xlv mens,nike lebron soldier ix mens

Post a Comment

You must be logged in to post a comment.