问题传送门

问题描述:

问一块蛋糕最少分成几份,才能使得既能给p个人平均分,又能给q个人平均分。

样例:

input:

2 3

output:

4

样例分析:

把蛋糕分别分成 1/3   1/3   1/6   1/6 份,如果是两个人的话就是 1/3 + 1/6 = 1/2 ,  如果是三个人的话就是 1/3    1/3    1/6+1/6=1/3.

所以最少是分成4份。

 

问题分析:

最容易想到的就是平分成最小公倍数份,但是显然,连样例都过不去。

要求是分最少的份数,不一定是平分。

就拿样例来说,答案4是怎么来的呢??

如果只有两个人平分的话,每个人是1/2.

如果只有三个人平分的话,每个人是1/3.

画两个图:

HDU1722-思维GCD

第一个蛋糕是切了两刀(我们规定每一刀都是沿半径切的,这样切几刀就能把蛋糕分几分

第二个蛋糕是切了三刀,因为要分成三分。

然后把这两个图拼在一起,第二个蛋糕虚线的那一刀。因为这一刀的存在,使得这个蛋糕既能平分成两份,又能平分成三分

所以可以理解为,先把这个蛋糕平分成两份,切了两刀。

然后把它平分成三分,需要切三刀,但是有一个位置重合了。

所以总刀数(也就是分的块数) 是 2 + 3 - 1 = 4.

要想使满足要求的块数最少,那么就要使两次切重叠的刀数尽可能的多

那么问题的重点就剩下,两次重叠的刀数最多是多少呢????

答案是 gcd(p, q).

假设先切了 k = gcd(p, q) 刀,那么接下来,不论是切成 xk = p块,还是切成 yk = q 块,一定不会再有重复的位置了

因为 x !=  y

#include <iostream>
#include <algorithm>

using namespace std;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}

int main()
{
    ios::sync_with_stdio(false);
    int a,b;
    while(cin >> a >> b)
        cout << a+b-gcd(a,b) << endl;

    return 0;
}

 

 

 

 

 


Simple And Clear