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。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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;
}
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信