问题描述：
问一块蛋糕最少分成几份，才能使得既能给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