问题描述:
问一块蛋糕最少分成几份,才能使得既能给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.
画两个图:
第一个蛋糕是切了两刀(我们规定每一刀都是沿半径切的,这样切几刀就能把蛋糕分几分)
第二个蛋糕是切了三刀,因为要分成三分。
然后把这两个图拼在一起,第二个蛋糕虚线的那一刀。因为这一刀的存在,使得这个蛋糕既能平分成两份,又能平分成三分。
所以可以理解为,先把这个蛋糕平分成两份,切了两刀。
然后把它平分成三分,需要切三刀,但是有一个位置重合了。
所以总刀数(也就是分的块数) 是 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; }
Comments | NOTHING