5322 - 数论:裴蜀定理:倒水(模板)

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?

如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许: 装满任意一个水壶 清空任意一个水壶 从一个水壶向另外一个水壶倒水,直到装满或者倒空

输入

输入三个整数X Y Z

输出

输出True或False,表示可以获得不可以

样例

输入

3 5 4

输出

True

输入

3 5 9

输出

False

提示

每个水壶只能灌满后,在水壶间倒腾

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题