HDU-1722 Cake 题解

题目大意

有一块蛋糕，可能要分给q个人或者p个人，问最少该切成多少块（不一定要相等大小），才能保证两者都可以分配。

解题思路

丢人啊。。

这还是新生的题目，新生都是一遍过的。。

我卡了好久。

自闭了。

其实想到了就很简单。

首先分成q块需要以圆心为中心切q刀，分成p块需要切p刀，但是他们中会有重复的刀不需要切。

所以答案就是$p+q-gcd(p,q)$。

至于为啥是gcd(p,q)，我稍微的证明了一下，不严谨。

设c=gcd(p,q)。

那么以第一刀开始，每次切的角度是$\Large \frac{2π}{\Large \frac{p}{n}}$。

同理，第二种是$\Large \frac{2π}{\Large \frac{q}{n}}$。

让两者相等，可以得到$\Large \frac{p}{q}=\frac{n_1}{n_2}$。

显然$p=c\times k_1,q=c \times k_2$。

所以有$\Large \frac{k_1}{k_2}=\frac{n_1}{n_2}$。

在满足这个条件下，右边是可以乘上1~n的，所以重复的就是gcd。

完整代码

#include <iostream>
#include <queue>
using namespace std;

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

int main() {
	int p, q;
	while (cin >> p >> q) {
		cout << p+q-gcd(p,q) << endl;
	}
}